Due date: 12/06 @ NOON

For this project, we do not allow collaboration between teams. You may only work with your partner and nobody else. We will use tools that discover non-obvious plagiarism to test for violations of this policy.

---

For this final homework, you can show how much you have learned: design by composition of functions, design by structural recursion, design by generative recursion, organization via local, design of abstractions, use of abstractions, the addition of accumulators. The homework counts for 5% of the total course grade (aka the instructor's whim). As you work on the project, imagine that we hand over your software to the graders together with a modification of the project description and the task to change your software accordingly. Naturally they expect the software to be designed well, that is, based on what you learned in 211 and they know where you live (or at least your email).

In order to accommodate the varying tastes of this class, we offer three rather different projects. Read them all carefully. Then pick one and design the solution carefully. Good luck.

Fighting UFOs:

Imagine you have become a game developer and your manager poses the problem of developing the first version of a War-of-the-Worlds game, freely named after H. G. Wells's science fiction novel. The purpose of the game is to prevent a UFO from landing on our world and from destroying the last available weapon. The screen shot on the right illustrates the successful defense of your world. The UFO descends from the sky. As it does, it randomly drops little bombs. If those bombs, hit the last available weapon platform, dubbed AUP, the player loses. The player also loses if the UFO reaches the ground unharmed.

The player owns an anti-UFO platform ({\sc aup}), which can move left and right on the ground. It reacts to left and right keystrokes only. A first keystroke causes the AUP to move continuously. Additional keystrokes accelerate the AUP, if the player uses the arrow key of the direction in which the AUP is heading; otherwise the AUP decelerates. With the uparrow key (and/or the space bar), the player can also launch anti-UFO missiles from the AUP. These shots go straight up at a constant speed. If any of them hit the UFO, it destroys the UFO.

Hints: Develop the game in stages:

1. Design the functions that move an AUP as directed by keystrokes.
2. Modify these functions so that the player can shoot. The shots should ascend from the middle of the platform.
3. Design the functions that simulate the UFO's descend to the ground.
4. Modify these functions so that the UFO's path is a random walk (zig-zag); it should never leave the canvas, however, and should not make large leaps.
5. Add functions that cause the UFO to release bombs at random points.
6. Integrate all the functionality.

Keep the design recipe in mind as you develop all these functions. Not following it will certainly get you into trouble here. Also compare with homework 8.

Drawing Family Trees:

Some people are intensely interested in their family trees. They collect as much data about their families as they can and often have someone create an elaborate drawing. Recently, web-based companies have designed programs that assists such people. Imagine yourself as a part of a start-up that provides software for drawing family trees.

Here is a data definition that describes ancestoral family trees:

(define-struct person (name mother father))
;; AFT = 'unknown | (make-node Symbol AFT AFT)

The goal is to develop a function that consumes such a tree and produces an image of the tree. The desired function should draw the tree with the root at the bottom of the canvas and the leaves toward the top -- the way it should be. In particular, the function should draw each leaf ('unknown) as a red bullet and each branch as the combination of two trees via a fork: see Problem Set 7 (Challenge). The family tree for the mother should appear on top of the left fork, and the family tree for the father should appear on top of the right fork. Overlay the name of the person on the join of the fork.

Design two such drawing functions: one using plain structural recursion and another one using an accumulator. Hint: to combine the two family trees, the first function will have to compute the width of the two subtrees and then pad the narrower one so that it is as wide as the other one. This suggests that you really want an accumulator that specifies how wide an image you expect back from your function. Naturally, as the function traverses the tree, the size should shrink properly.

Finally, design a third drawing function that draws the tree the way "stupid" computer scientists draw trees, with the root at the top and the tree growing downwards.

Your final product should consist of three function definitions plus all those function definitions that are used by at least two of the main functions. It must not contain any other function definitions.

Studying Work Processes:

You are working for a consulting company that helps other companies arrange their process flow. Boston Harbor, Inc. has hired your company to study the construction of new docking stations for ships. Your task is to create a program with which your operations research specialists can study queuing behavior in the harbor.

The harbor has a fixed number of docking stations (5). The long-shore men unload ships at varying rates; on the average, some 2 to 12 ships leave the harbor on the hour. This is known as the death rate. Fully loaded Ships arrive at the rate of 3 to 10 per hour. This is known as the birth rate. They line up in a queue outside the harbor. The length of the queue depends of course on the birth rate, the death rate, and the harbor's docking capacity. (We assume that the workers have a strong union and we can't change their behavior.)

The purpose of your program is to run a simulation and to display the current situation in a rather simple form:

The first slot represents the current time unit, the second the number of arriving ships, the third the number of ships in the queue, the fourth the number of currently utilized docking stations, and the last one the number of ships leaving the docks.

Make sure that it is easy to run simulations for different birth rates, death rates, and number of docking stations.