Imagine that you are creating a pocket calculator. You have created the functionality for all the buttons except x ², the button that squares a number, and exp, which allows you to calculate base^exponent, where exponent is an integer. You may use any other functionality a calculator would normally have: for example, (+, -, *, /, =).

In the third-grade math class of French mathematician Carl Gauss, the teacher needed to give the students some busywork. She asked the class to compute the sum of the first 100 numbers (1 to 100). Long before the rest of the class had finished. Carl raised his hand and told his teacher that he had the answer: 5,050.

A palindrome is a word or phrase that reads the same way forward and backward, like “racecar.” Describe a sequence of steps that determines if a word or phrase is a palindrome.

Consider the three mazes shown in Figure 1-3. Describe two different algorithms for solving a maze. Discuss advantages and disadvantages of each algorithm. Then look at the maze and predict which algorithm will complete first. See if your predictions were correct by applying your algorithms to the mazes.

Figure 1-3. Three mazes for Exercise 4

Figure 1-4 shows an alternative way to represent an algorithm. (Note: we introduce this construct in detail later on. If it looks too intimidating, skip it until after you’ve read Chapter 4.)

Figure 1-4. Alternative representation of an algorithm for Exercise 5

A cable company must use cables to connect 15 homes together so that every home is reachable by every other home. The company has estimated the costs of different cable routes (Figure 1-5 shows the numbers associated with each link). One engineer provides an algorithm, shown in Figure 1-5, that will find the cheapest set of routes to pick. Does the engineer’s algorithm work for this case? Why or why not?

Figure 1-5. Cable company dilemma for Exercise 6

Engineer’s Algorithm: