Broadening the Teaching of Theory

Offhand, I can think the following primary "types" of computer science classes:

1. Classes specialized for graduate students in a subfield (e.g., theory, or usually the next level down, e.g. cryptography, pseudorandomness).
2. Classes for graduate students in CS.
3. Classes specialized for undergraduate CS majors.
4. Classes for undergraduates primarily in other sciences.
5. Classes for general, non-science undergraduates.

I think most CS professors naturally gravitate to teaches types 1 and 3 -- classes in their area of specialization. I think, as a community, there is generally at least some effort by theorists to broaden the scope of some at least classes to types 2 and 4. Certainly I try to encourage non-CS majors into my undergraduate algorithms class -- what scientist shouldn't be learning to think algorithmically? -- and to get non-theory graduate students to take my randomized algorithms and algorithms at the end of the wire courses. I suspect, though, as a community, we could be doing more. While personally theory seems less isolated within CS today to me than it did say a decade ago, there still seems to be plenty of bridges left to be built.

Perhaps more challenging is classes of type 5 -- classes for non-scientists. The question of how to design a science distribution requirement course for non-scientists is not specific to computer science, but in CS it perhaps especially challenging. Programming is often taken to be off-limits, since how much worthwhile programming can be taught to people who have never seen a computer program before? And theory seems to require too much math. Plus there is the age-old question of how to make it all relevant to non-scientists.

Harry Lewis co-designed a course, Bits, which I think is a great example of what's possible, and is the course I wish I could have designed, if I wasn't so busy teaching my regular classes. I enjoy this first paragraph from the course description:

This is a course about information for students who are not technically or mathematically oriented. It aims to explain the dramatic increase in the amount of information that is being communicated and stored, and the consequences for society of that increase in capacity.We are on the cusp of a revolution, potentially as consequential as the invention of printing or the replacement of animals by steam engines as the vehicles of transportation.The course aims to equip those who will determining policies, whether as legislators, corporate leaders, or ordinary citizens in their multiple roles, with an awareness of the choices that lie only a short time ahead of us.

I am also strongly biased in that Harry followed my advice, with much of the technical meat in the beginning of the course covering basic information theory, specifically compression and coding. (Note: I emphasize that Harry followed my advice, not that he took my advice. As far as I know, he always planned to structure the course this way, and it's just happenstance that his take on what was worthwhile matched mine. I'm pleased nonetheless.)

The course is an interesting mix of science, technology, and policy. The lectures are now apparently freely available online now that the course is over for those who want to see it. Someday, perhaps I'll get to design a course like this. I'd be curious to hear from others what other examples there are for CS-based courses with non-trivial technical content meant for non-science majors. (Jon Kleinberg's course new course comes to mind, but it really seems to be type 4, built for scientists, including mathematically oriented economists and sociologists.)