Tuesday, December 02, 2008

programming assignments

Inspired in part by Michael Mitzenmacher's exhortation:

  • compile-time errors
  • failure to terminate in the prespecified time limit
  • incorrect answers
  • run-time errors
  • all correct answers
What worked:
What didn't:



  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.

  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.

  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.

  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.

  5. This comment has been removed by the author.

  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?


  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.

  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.

  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.

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

  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.

  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.


    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?

  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.

  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!

  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.


Disqus for The Geomblog