Tuesday, December 02, 2008

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

17 comments:

  1. If you're not already aware of it, you might be interested in Project Euler. Theory/math problems where the answer is reduced to a single integer. The harder ones are very cleverly chosen.

    ReplyDelete
  2. I also just did something similar in a course based on the Kleinberg–Tardos book, but avoided the on-line judge. I gave the students lots of files with matched input-output pairs for each assignment, to they basically evaluated their own code. This makes the task a lot easier for them (because they can do aggressive and constructive debugging, instead of reacting to the one-bit responses from the online judge) and burdens me with minimal technical problems. Students were also allowed to use any programming language they wanted, which would not be possible with the online system.

    Another problem with the programming contest exercises is that you can find crisp solutions online using google. So I felt I had to cook up my own programming exercises anyway.

    ReplyDelete
  3. So do it.

    Think through, reasonably systematically, what the major algorithmic questions in computational geometry are. Then think through how to construct examples that would fail with a naïve implementation and work with a good implementation.

    I imagine things like
    "Given a points sequence defining a polygon and a point, write a function to determine whether the point is inside or outside the polygon" and then have "official" test cases with the more obvious things to feed into the algorithm, and a "grading" test case with, say, very many edges... Or "Given a sequence of points defining a polygon determine whether it is convex", with similar choices.

    It seems like it would be a bit of work to do the ground work, as it were, but a reasonable amount for a geometer who knows the field, and one that might well generate a LOT of interest once it exists.

    Things like the grading server already exist, and it probably is rather easy to configure it to deal with new problems, so it's really about the problems more than the technology.

    ReplyDelete
  4. 1. The reason you don't get details for a run-time error, time-limit exceeded, and wrong answer is that almost any further detail can be exploited to reverse engineer the test input and it's supposed to be your job to design your own tests and make sure your program works. In fact, even the fact that there are three possible failures gives you lg(3) bits of information about the input :) and can be exploited. But it's a bit too painful.

    2. The test data is not always great. For example, I "solved" an SCC problem on that online judge (best time&space usage, even) before embarrassing myself by "proving" a wrong algorithm on my blog.

    3. On http://spoj.pl you can setup your own problems (if you send an email and ask for the right to do it) and you can write custom validators. This sounds like the easiest way to go for your randomized algo assignments.

    4. The most common Java "slowness" is the I/O. In fact, it's not really slow: If you use C-style functions (e.g., get one char at a time) then you get similar performance. You are penalized only when you use higher level abstractions like Scanner. So if you give the students one Java function that reads integers quickly you get rid of 90% Java performance problems.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Suresh,

    I also think a change like this would benefit Penn State students (more generally, theory should be incorporated into the intro programming sequence and programming should be a part of the theory courses).

    But, a question:

    Did you change the wording of the problems at all? I've found that resourceful but lazy students often go looking for solutions online. (I've found that for theoretical problems; I imagine it would be worse with short-answer programming questions).

    That entails a lot of effort rewording (or inventing) problems so they still sound natural but don't match the original too closely.

    (How) did you handle this?

    -adam

    ReplyDelete
  7. Hi Suresh,

    I'm not sure if you're aware, but I just wanted to let you know there are several other online judges that are nice: http://www.spoj.pl/, http://acm.uva.es/problemset/, http://acm.sgu.ru/, and http://acm.zju.edu.cn/onlinejudge/. I personally prefer SPOJ. You said you might consider designing problems from scratch in the future. If so, you might want to try contacting the SPOJ development team (contact@spoj.pl) to be granted permissions to upload your own problems. You can then log in SPOJ as a judge and view all code submissions to your problems, and students both in your class and around the world can learn from the problems you create. SPOJ also lets you put problems into a timed contest, if you have use to do so.

    ReplyDelete
  8. "You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program. " Alan J. Perlis

    Encourage your students to visit www.topcoder.com, where programming contests are organized on a platform similar to the one you use. There is an "algorithm" category, and people who shine there are hired by G**gle and other companies.

    ReplyDelete
  9. ACM competitions are lots of fun. Your requirement might get some of your students interested in programming contests, which will have the side benefit of making students much better prepared for interviews with tech companies.

    ReplyDelete
  10. There's stuff like the Sphere Online Judge, Project Euler, and of course TopCoder...

    ReplyDelete
  11. What algorithms in a computational geometry course would you turn into programming assignments?

    The kind of basic functionalities that need to be available to students depend on the answer to this question. I wonder if this is the main bottleneck in actually doing this.

    ReplyDelete
  12. Take a look at the algorithm competitions at http://www.topcoder.com/tc. They have well designed problems, and a very nice server side compilation/editing environment. I don't think they keep stats on execution time, but instead have a hard execution time limit for problems. Getting under the limit often requires some pretty deep thinking about algorithms.

    One downside, from an instructor's viewpoint, is that solutions are available for all old problems.

    The focus of the site is on live competitions, where everyone has the same 90 minutes (or so) to complete 3 problems. But all old problems can be worked on anytime using the same software, as long as there is no live competition going on.

    ReplyDelete
  13. 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.

    Obviously it's easy to test for correctness and performance...so what else are you evaluating? Or do you mean the lack of a batch operation is what's painful?

    ReplyDelete
  14. You can consider using an online judge other than that one (UVa's); I can tell you from experience that Sphere Online Judge is far more reliable and less flaky, and has clearer problem statements and I/O specifications. It also has lots of computational geometry problems, like BSHEEP and FSHEEP, but they're somewhat hard to find...

    Some other online judges let you organise your own "contests", though, where you can upload your own problems and test data, and have looser time limits. That might help with the Java problem, and even to simplify grading.

    ReplyDelete
  15. Is it really the case that DS&A classes in the U.S. do not have compulsory programming exercises to implement some of the more fundamental data structures and algorithms?! WTF? No wonder a majority of the programmer applicants I see are totally unfit for anything but flipping burgers!

    ReplyDelete
  16. During my undergrads, my learned a lot about algorithms by participating in the ACM online judge. The problems there really provide good understanding of an algorithm. But as a past participant as well as a contributor to the problemset archive, I warn you about one problem of using the system for course assignments: there are many active "code-exchangers" out there, who check the online status to locate people who want to exchange source codes.

    ReplyDelete

Disqus for The Geomblog