CMSC 15100: Lab 4

You’ve learned about trees in class. One extremely important use for trees is for mad scientists to use in helping them genetically engineer mice that are good bowlers so they can win the Statewide Mad Scientist Mice Bowling Cup. To that end, they need to keep track of each mouse’s parents and bowling average:

; A mouse is (make-mouse name bowling-average)

; where name is a symbol and bowling-average is an integer

; in [0, 300].

(define-struct mouse (name avg))

; A mouse-bowler-tree is either

; (1) a mouse or

; (2) (make-tree mother father some-mouse)

; where mother and father are mouse-bowler-trees

; and some-mouse is a mouse.

(define-struct tree (mom dad mouse))

Mad scientists use the first mouse-bowler-tree variant to represent the “seed” mice from which they engineer their population of skilled bowlers; the heritage of these initial mice is unknown because pet stores keep poor records. The second variant represents the offspring of the scientists’ controlled breeding program, and for these mice, the parents are always known.

1 Examples

Define two mouse-bowler-trees, each with at least five mice.

2 Best bowling average

Define a function best-bowling-average, which takes a mouse-bowler-tree and returns the best bowling average of any mouse in the family represented by the given tree.

3 Predicted bowling average

An important part of the (mad) science of genetic mouse engineering is knowing how your experiments are affecting your subjects. In this case, that means knowing how much better or worse a mouse is doing relative to what you would predict. A mouse’s predicted bowling average is the average bowling average of all that mouse’s known ancestors. When a mouse’s pedigree is unknown (i.e., when it’s represented by the first mouse-bowler-tree variant), its predicted average is assumed to be the Universal Mouse Bowling Average Average, standardized by the Mad Scientists’ Bowling League to be 50.

First define an extended-mouse-bowler-tree data type that holds all the information a regular mouse-bowler-tree, plus for each mouse the difference between its actual (measured) score and its predicted score (i.e., the average score of all of its ancestors). Then write the function extended-tree, which produces an extended-mouse-bowler-tree from an mouse-bowler-tree.

4 Beating the average

Write the function most-exceptionally-good, which takes a mouse-bowler-tree (not an extended-mouse-bowler-tree) and returns the name of the mouse whose bowling average is greater than its predicted average by the greatest amount.

5 Submitting your work

Submit your work by Friday night using the hand-in tool built into DrScheme. If you worked with a partner, you must submit twice – once under each partner’s name – and each submission should include a comment listing the partners’ names.

6 Credit

This exercise is a revision of one written by Jacob Matthews.