## 22 June 2007

### Programming Assignments

Michael Mitzenmacher started his blog, My Biased Coin, with a series of posts entitled Cuckoo Hashing, Theory and Practice. His last post is about teaching and so it is less informative and more likely to generate noise such as this post. David Eppstein has some thoughts on the matter on his own blog.

So what is the matter? Universities should do a better job connecting theory to practice.

I guess most people would agree with the above. For different reasons. Some will say that universities should produce programmers for the software industry and instead they produce people that hate mathematics and don't know how to program. Universities should just teach students how to program using the modern technologies developed in the industry. These are industry people (mostly managers). Some will say that students that go to CS departments know how to program and generally like computers, but the theory courses fail to make a connection. This is Prof. Mitzenmacher (and some others who teach theory, I suspect). Some will argue that blending theory and practice just makes one's days more fun. This would be Prof. Knuth. No matter what the reason is, I believe there is strong agreement that universities should do a better job in connecting theory to practice and vice-versa. (Of course, university really means CS departament, or, perhaps, we can include math.)

So how should we do it?

Mitzenmacher proposes programming assignments. Eppstein proposes using a real programming language (Python) for writing pseudocode. Mihai (Pătraşcu?) proposes less rigor and a problem-oriented approach. Cristopher Moore proposes having a project that uses a few algorithms (as opposed to many assignments that cover each only one algorithm). Almost all want better textbooks.

Last semester I was a demonstrator for part 2 of a Data Structures and Algorithms course at UCD taught by Simon Dobson. He already had weekly programming assignments. I was somehow unhappy that for part 1 most students submitted huge pieces of code that did not even compile. I felt this is just unacceptable. You can't really enjoy programming if you are just typing stuff without compiling and experimenting. So I developed an evaluation website and adjusted the problems by completely specifying the input/output format. The idea was that students would have to submit something that works. But we ended up giving points for compiling and for working on small tests because, for each assignment, only about five out of one hundred students were able to solve it. I thought the assignments are too hard but Simon disagreed. Overall, I think this was a good experience. My opinion is that the biggest improvement we can do to this course for the next year is to enforce a strict policy in the lab: Only people working on the assignment are allowed. By the end of the last semester virtually all students spent their time browsing the internet, especially on social' websites. But I digress.

All courses should be fun! Alas, what is fun for one student is not fun for another. Moreover, asking students what is fun doesn't work. They tend to have a wrong idea about it while they are in college (no homeworks, more trips to the nearby pubs, more jokes in the classroom, no Greek letter, no grades, and so on). Probably the best we can do is to ask students their opinions after the course and after graduation. The next best we can do is to tell our own stories and collect them.

The reason I liked programming was that in BASIC I was able to easily draw — much better than I could by hand. I was six and my hand was shaky. On the other hand the circles and the lines on the screen were perfect. Sure, I needed to figure out how the numbers I plug in affect what is drawn, but that was nice — it felt like magic! The reason I liked algorithms was that I tried to solve a problem for one week (shortest path in a graph) and failed. In the process I come up with a backtracking implementation that worked for 20 nodes but all other things I tried failed. I was convinced that it is impossible to deal with graphs that have 40 nodes. I still remember the feeling of awe I had while reading a description of Dijkstra's algorithm from Tannenbaum's Computer Networks book. I went straight to the keyboard and implemented it because I needed to see it. Oh, I forgot to mention that this was actually a real problem that my father had at work and I didn't really know that that data is a adjacency matrix of a graph and that what I am looking for is called shortest path.

Because of my experience I think that problems are good. Give students a small problem that they can handle, to build confidence. Then increase the size of the input and let them try hard. Then show them a solution. Make sure they feel that the solution is within their grasp and they would have got it' if only they were a bit lucky or more thorough. Except that, well, I don't think this would work in a classroom scenario. It is likely that most students won't solve the `hard' part and the smart ones would use advanced development tools to find a recipe on the Internet before they really try. And really trying is what makes you really appreciate a solution. This is why the usual style of presenting theorems before proofs is good. It gives people a chance to try to find the proofs themselves. Any ideas on how to make this approach usable in classroom?

Now about textbooks. Many complain that CLRS is too theoretical. I thought it was quite entertaining and well written. And it made me write more programs than I would have otherwise. There is a caveat. I didn't use it for a course. (I didn't take any course in algorithms since I studied EE. Well, signal processing algorithms are algorithms, but you get the point.) I bought it after my adventure with Dijkstra's algorithm but somehow kept it on the shelf. I started reading after some guys looked at me in a strange way after I asked them what is Dynamic Programming. While I was solving the exercises I always wrote a program. I actually thought that's implied and there is no way someone would consider only a paper sketch to be a solution.

And finally, about using a real programming language instead of pseudocode. Oh, yes, yes! I like it. That description should come accompanied by a second alternative description, probably in English. I think that not only textbooks and lecturers should use a real programming language instead of pseudocode but even papers! I guess that twenty years ago it wasn't feasible to do so but now there are plenty of programming languages that are about as easy to read as pseudocode. Using a real language makes the presentation more precise. Sometimes no real programming language would look as nice as pseudocode and in those situations I think it is perfectly acceptable to omit some obvious optimizations and special cases that arise from implementation issues. (For example, in Nemerle hashtables that map something to integers insist that you should insert the key before incrementing the value, which makes them less convenient than C++ maps for counting things.)