Programming in theory class

Michael Mitzenmacher has another interesting post up, on programming in theory courses. I don't see a way to comment directly on his blog, so I'll put some of my own thoughts on the subject here:

• At UCI, we're on a quarter system, and there's only one quarter of required theory (more specifically, algorithms) in our undergraduate major. Ten weeks is simply not enough time to include both the theory I want to cover, and programming on top of that. We do have a separate algorithm implementation class that Dan Hirschberg teaches as an elective.

• Despite not wanting to add programming assignments to our algorithms course, I feel strongly that the students should understand that the reason for studying algorithms is for their use in programming, rather than as an obscure and abstract branch of mathematics.

• Partly for this reason, when I describe algorithms in pseudocode, I use a pseudocode syntax closely related to Python, sometimes so close that what I describe is actual runnable Python code. Why Python? Because its high level, indentation-based block structure and lack of variable declarations makes it already look very similar to pseudocode, and I think writing pseudocode in a way that is already very close to code helps the students understand the connection between theory and implementation.

• In terms of textbooks, I see the lack of connection to programming as a major weakness of CLRS. I feel that it describes the algorithms as mathematical entities that the students are supposed to find interesting per se, and doesn't really talk about implementation of algorithms or even give sufficiently concrete scenarios for the usefulness of the algorithms described. And the lack of focus on implementation causes problems for some of the description of the more advanced algorithms (e.g. where are the flow values and residual capacities stored in the network flow algorithms) making it difficult to implement them from the descriptions provided.

• The textbook I use for my undergraduate algorithms classes is "Algorithm Design" by Goodrich and Tamassia. It includes implementations in Java at the end of each chapter, which I largely ignore in the lectures but could be helpful to any students who actually read the text. But more importantly I think it does a better job of covering the connection between algorithm and implementation. And it's not as comprehensive as CLRS but there's plenty of material to fill a quarter and cover the essentials. (Disclaimer of bias: of course, one of the authors is also a colleague at UCI and a frequent coauthor.)

Comments: