Nifty Assignments

Nifty Assignments is a Stanford project collecting a number of interesting assignments usable in a variety of CS courses. This page gathers some of them that we might be able to adapt for lab assignments, or at least use as starting points.

In rough descending order by probable suitability:

• Estimating Avogadro's Number

  Process some images representing experimental data to come up with Avogadro's Number.

  Operates in several stages; may be good for a pipeline assignment. Combines a few different calculations such as depth-first search and nearest neighbor.

• Spreading of Fire

  A cellular automaton, simulating the spread of fire, taking into account environmental conditions. Could be a good example of stencils, and would be more novel than Conway's Life.

• Catching Plagiarists

  Given a sizable corpus of documents, find the pairs that share the most six-word phrases.

  Very algorithmic, very scalable. Not entirely clear that it's unembarrassingly parallel, and the problem has an asymptotic lower bound of Ω(n^2) (obtainable the obvious way), but might be worth thinking about nonetheless.

• Boggle

  Various search procedures for the Boggle word-search game.

  This could be done naïvely in an embarrassingly parallel fashion, but optimizing might be an interesting problem, especially if we increase the size of the board. Also, there are multiple graphs being searched (the dictionary trie and the board), with locality properties that may be worth exploring.

• Minesweeper

  As is, probably not good for our purposes. But Minesweeper verification—finding whether a given board state is consistent—may be something. It'd be a rather unpredictable search problem (though, again, there's an embarrassingly parallel brute-force method).

• Quilt

  Arrange graphical tiles in a repeating grid, with specified variations (colors, etc.).

  Probably too simplistic for us as is, and we probably don't want graphics. But it is one way to get at iteration besides “go through this data structure,” and maybe we could introduce data dependencies to make things more interesting.