Class Notes for Weds, 10.13.2004

Activity:

Break up into groups of 2 or 3. Find a computer so that you can consult the notes.

Produce a design for a program that plays the game of 15. The program has to be able to play first or second.

The rules of the game are:

There are two players.

Start with 15 chips.

Each player in turn takes 1,2,or 3 beans.

The player who takes the last bean wins.

Develop your design in the following way:

1. Think of a strategy for playing the game. This could be "always take 2 chips", or "always take the same number your opponent took, or 2 on the first move", or something better.

2. Besides playing your strategy, work out what else the program has to do. For example, how will it be determined whether the program or the human player goes first in a given game? Does the program determine that the game is over? Should the program determine who won? Should it check that its opponent's moves are legal?

3. Now imagine what the program has to do to play the game this way. DO NOT write code, but think about how you can decompose the whole job into simpler steps. Use the three main ways to break a problem up that are presented in Notes 6: sequence, conditional, and repetition.

4. Make an outline or diagram of your program, as shown in Notes 6. You do not have to follow exactly the conventions shown there, but your decompositions must be clear.

After 30 minutes, put two of the outlines or diagrams on the board and critique them.

Some questions to ask:

(a) Are the designs clear and complete? Do they use the requested types of decomposition?

(b) Would they work correctly, if converted into programs?

(c) Which strategy would win if they were played against each other? (This would be done by telling one program that it was to play first, and the other that it was to play second, and then typing the moves of the first program into the second program, and vice versa.)

If time permits, and only if time permits, write code that implements one of the designs.

Friday, 10.15

Get closure on Weds' exercise, if design discussion not complete (don't do the coding.) Then, if time permits, do more design practice, as for Wednesday. Remember, NO CODE!

Use these problems:

(1) The Babylonians developed the following way of approximating the square root of a number, say 2. They made a guess, say 1. They divided 2 by the guess, getting the sibling of the guess. They averaged the guess and the sibling to get a new guess. If the new guess was within some tolerance, say .0001, of the previous guess, they stopped.

Design a program that asks the user for a number to find the square root of, and a tolerance, and produces an approximation using this method.

Note: You should find it fairly easy to rough in the top level steps here, and the repetition. But how are you going to control the repetition? Hint: Assume you can have a step that breaks out of the repetition.

(2) Design a program to play tic-tac-toe.