본문 바로가기

컴퓨터/Data Structure/Algorithm

[Programming Challenge] 1.7 Hints

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.