programming assignments

Inspired in part by Michael Mitzenmacher's exhortation:

Here's my claim: theory does untold damage to itself every year by not having programming assignments in the introductory classes on algorithms and data structures.

I tried an experiment in my algorithms class this year. Using the ACM programming competition online judge as an evaluation tool, I assigned one programming assignment in each of the first three assignments in my class (later assignments went into approximations and randomization, which the site didn't really cater to). Coupled with this, I used the ACM Programming challenges book by Skiena and Revilla to guide my choice (they break the problems down nicely by dominant technique).

The way the system works is this: you're given a problem definition and an input/output specification. You write your code in one of three languages, using a specific compiler flag sequence, and then upload your code. The system runs your code through a battery of tests, and then reports whether you had

• compile-time errors
• failure to terminate in the prespecified time limit
• incorrect answers
• run-time errors
• all correct answers
  

What worked:

• Students actually liked the idea of programming assignments: I received numerous variations of the comment, "I didn't understand the algorithm, but once I coded it...". They were less enthused by the server, but more on that later.
• People started getting quite competitive: the site maintains stats on the best implementation thus far, and even after students satisfied the requirements of the assignment, by matching the desired time limit, they tried to optimize their code further.
• The questions are well-designed, and usually need algorithmic tricks rather than hacks. For example, one question is to compute the closest pair, and any optimized brute force algorithm will fail, but the standard deterministic divide and conquer will work fine.
  

What didn't:

• The server would occasionally flake, especially a few hours before assignment deadline time :)
• I/O specifications were often tricky: the problem specifications would leave out details about what one could assume about the input, so simple things like "don't assume that when a range [x,y] is given in the input, that x <=y" needed to be discovered.
• The error messages are cryptic to a fault. Compile time errors are linked to the point in the code where this happens, but for any other kind of error, you are merely told that an error occurred. This caused major frustration.
• With Java especially, getting a correct implementation within the time bound seemed harder than with C/C++. Since Java is often the first language students learn, this is annoying, especially since the whole point of such exercises is to abstract away as far as possible the particular idiosyncracies of a language.
• From a grading point of view, it's very painful to evaluate each person's submission. There's no easy way except to do it manually.
  

Overall, my experience was mixed-to-slightly-positive: I'll probably do this again, but I might also include examples where I design the test inputs and do local evaluation. For some problems (like with randomization) I might have to design the problem from scratch.

Now what I'd like is something similar for my computational geometry class :)