Student Programming Projects

[Andrew J Bromage]

G'day all.

On Fri, Nov 02, 2001 at 11:52:04AM -0500, Barbara Nostrand wrote:

> I posted this message a while ago and got a few suggestions that
> sounded like they would maintain student interest. Alas, my disk
> drive crashed soon thereafter. So if you have given me suggestions
> before, please do so again. I was particularly intrigued by the
> suggestions put forth by someone who complained that someone
> else's suggested projects were too theoretical.

That may have been me.  IME, there's only so much theorem proving
to which you can subject an undergraduate before they switch off.

My suggestion is to look to the other subjects that they've done and
raid them for ideas.  For example:

 - If they know about DFAs and regular expressions, get them to
   implement a cut-down version of Lex.  (I have a really neat DFA
   construction method tucked away which is much more "algebraic data
   type" than the one you get taught in the Dragon Book.  It's also
   much faster.  Available on request.)

 - If they know about graphics, get them to implement a simple ray
   tracer.  Limit yourself to one kind of geometry (say, spheres)
   but allow different kinds of light source and surface material.

 - If they know about game playing, alpha-beta search, heuristic
   search, get them to implement a program which plays some one-
   or two-player game and let them compete against each other (in
   one-player games, lowest average and/or worst-case number of moves
   wins some small prize, use runtime to break ties).  Some suggestions
   for games of about the right complexity: "Mastermind", 15-puzzle.

 - If they know about Unix, get them to implement a program from the
   standard environment, like diff(1).  (Provide or point them to an
   algorithm for longest common substring first, of course.)

 - If they know something about numerical analysis (or even if they
   don't), how about a program to perform numeric integration of a
   function?  Gauss-Konrod quadrature with binary subdivision tends
   to be quite easy to understand.

 - If they've been introduced to the class NP, get them to try to solve
   an NP-hard optimisation problem.  Impose a time/resource limit.

Whatever happens, give them a project that they can see the practical
use of, or if not, that they can play with.

Cheers,
Andrew Bromage