1.7 Hints
1.3 Who should get the extra pennies if the total does not divide evenly?
1.5 How do we best handle the fill command? Is it easier to keep separate copies of
the old and new image?
1.8 Notes
1.1 The 3n + 1 (or Collatz) problem remains open to this day. See Lagarias [Lag85]
for an excellent mathematical survey. An international conference on the Collatz
problem was held in 1999; see http://www.math.grinnell.edu/∼chamberl/conf.html
for the online proceedings.
1.2 The Minesweeper consistency problem takes as input an n × n rectangular grid
with the squares labeled by numbers 0 to 8, mines, or left blank, and asks: is there
a configuration of mines in the grid that result in the given pattern of symbols,
according to the usual Minesweeper rules? The Clay Institute of Mathematics
(http://www.claymath.org/) offers a $1,000,000 prize for an efficient algorithm
which solves this problem.
But don’t get too excited! The Minesweeper consistency problem has been
proven NP-complete [Kay00], meaning that no efficient algorithm for it can exist
without revolutionizing our understanding of computation. See [GJ79] for a
thorough discussion of NP-completeness.
1.6 Software-interpreted virtual machines are the key to the portability of languages
such as Java. It is an interesting project to write a simulator for the machine
language of an old, obsolete, but simple computer such as the PDP-8. Today’s
hardware is so much faster that your virtual PDP-8 will significantly outrun the
original machine!
1.7 Once you have written a legal move generator (the essence of this problem) you are
not very far from building your own chess-playing program! See [New96, Sch97]
for stories of how computer chess and checkers programs work and beat the human
World Champions at their own games.
1.8 The mathematics of voting systems is a fascinating subject. Arrow’s impossibility
theorem states that no voting system can simultaneously satisfy all of five
obviously desirable properties. See [COM94] for an interesting discussion of the
mathematics of social choice.