Monday, October 15, 2007

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.)


asarwate said...

More on the comm/info theory side of things, there's a class at Princeton on wireless that was apparently one of the most popular classes on campus -- it was also a mix of technical, policy, and culture surrounding wireless communications. Vince Poor was in charge of it.

Unknown said...

There's another class at Princeton taught by Kernighan (see here) for humanities & social sciences majors. According to the webpage,

"COS 109 is intended to provide a broad, if rather high level, understanding of how computer hardware, software, networks, and systems operate. Topics will be motivated by current issues and events, and will include discussion of how computers work; what programming is and why it is hard; how the Internet and the Web operate; and how all of these affect security, privacy, property and other issues. We will also touch on fundamental ideas from computer science, and some of the inherent limitations of computers."

Anonymous said...

I love teaching Bits. But I can't take sole credit for it --- Hal Abelson has helped me with it, and he has an unerring sense of why stuff matters. Also Ken Ledeen, a longtime friend and colleague who is a local software consultant. The three of us are writing a book aimed at an even bigger audience, trying to inform the public about decisions that are being taken without public involvement or even awareness. It's to be called "Blown to Bits: Peril and Promise of the Digital Explosion." It should be out this spring. (On the assumption we finish writing it, that is.)

The big challenge in teaching this course is persuading the non-science students who take it that they are actually capable of understanding the material and reasoning through the problems. They are perfectly smart but they are used to doing math by table-lookup, as it were, slotting the SAT questions into one of a finite number of categories and pulling out the corresponding equation. So they have a lot of trouble with a question that doesn't correspond to any part of high school math, such as, "If it takes a year to crack a 32-bit key, how long would it take to crack a 64-bit key? How long would it take in five years, if Moore's law continues to hold?" The official rubric of the course is "Quantitative Reasoning," which is exactly right. It teaches people to think quantitatively, a skill it sometimes seems they lost around the time they entered high school and started their SAT preparation.

The other thing that has been great about teaching this course is that I've been able to get in terrific guest lecturers. I got MA congressmen who are very concerned about privacy and telecomm legislation. I got a guy from a spook agency. I got Harvard and MIT librarians together to do a panel on the future of libraries.

Finally, every student has to do a project, and they have to do them in teams. The projects require going out into the field and talking to people whose lives are changing because of the revolution. So we had a great project on dairy farming (some are flourishing because of automation, some are going out of business) and another about used book stores (ditto). This was the best part of the course for several students, as it made things much more real, and they'd never taken a course that involved anything but library research.

Anonymous said...

I'm not sure that the only way to make material relevant to non-computer scientists is by picking "real world" examples that demonstrate ideas. I suspect it suffices to communicate concepts using visual intuitions.

It has been my experience that the "Theory of Computation" is an utterly incomprehensible block of material to most people (including majors as often as not) when taught with most textbooks. However, there is a drastically different response with Michael Sipser's book which does a great job of getting across the key ideas without getting bogged down in the subtleties.

Anonymous said...

I should have stressed that my Bits course is really about information theory and communications theory, not computability theory or formal systems. It would be tough to teach that material to non-scientists - unless they were philosophically inclined.

Anonymous said...

Sanjeev Arora taught a course called "The Computational Universe" at Princeton aimed at non-majors. See the page for the course blog:
I think it actually included theory of computation material such as the Halting problem.

Its description is the following:

Computers have brought the world to our fingertips. We will try to understand at a basic level the science -- old and new -- underlying this new Computational Universe. Our quest takes us on a broad sweep of scientific knowledge and related technologies: propositional logic of the ancient Greeks (microprocessors); quantum mechanics (silicon chips); network and system phenomena (internet and search engines); computational intractability (secure encryption); and efficient algorithms (genomic sequencing). Ultimately, this study makes us look anew at ourselves -- our genome; language; music; "knowledge"; and, above all, the mystery of our intelligence.