Chapter 1. Introduction
When I was 12, my brother and I studied piano. Each week we would make a trip to our teacher’s house; while one of us had our lesson, the other would wait in her parlor. Fortunately, she always had a few games arranged on a coffee table to help us pass the time while waiting. One game I remember consisted of a series of pegs on a small piece of wood. Little did I know it, but the game would prove to be an early introduction to data structures and algorithms.
The game was played as follows. All of the pegs were white, except for one, which was blue. To begin, one of the white pegs was removed to create an empty hole. Then, by jumping pegs and removing them much like in checkers, the game continued until a single peg was left, or the remaining pegs were scattered about the board in such a way that no more jumps could be made. The object of the game was to jump pegs so that the blue peg would end up as the last peg and in the center. According to the game’s legend, this qualified the player as a “genius.” Additional levels of intellect were prescribed for other outcomes. As for me, I felt satisfied just getting through a game without our teacher’s kitten, Clara, pouncing unexpectedly from around the sofa to sink her claws into my right shoe. I suppose being satisfied with this outcome indicated that I simply possessed “common sense.”
I remember playing the game thinking that certainly a deterministic approach could be found to get the blue peg to end up in the ...