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