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-bowler-tree is either
(1) empty or
(2) (make-mouse father mother name bowling-average)
where father and mother are mouse-bowler-trees, name is a symbol, and bowling-average is a number between 0 and 300.
Part 1 Write a data definition and template for mouse bowler
trees. Then define two mouse bowler trees each with at least 5 known
mice. Also add this definition:
;; Oldest Generation: (define Mickey (make-mouse empty empty 'Mickey 168)) (define Minnie (make-mouse empty empty 'Minnie 90)) ;; Middle Generation: (define Speedy (make-mouse Mickey Minnie 'Speedy 210)) (define Danger (make-mouse Mickey Minnie 'Danger 37)) (define Suzy (make-mouse Mickey Minnie 'Suzy 100)) (define Mighty (make-mouse empty empty 'Mighty 190)) ;; Youngest Generation: (define Maus (make-mouse Mighty Suzy 'Maus 120))
Part 2 Define a function best-bowling-average, which takes a mouse bowler tree and returns the best bowling average of any direct ancestor in the family (or 0 if the tree has no members). Then define a function worst-bowling-average, which takes a family tree and decides what the worst bowling average in the family is (using 300 if the tree has no members).
Part 3 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 ancestors. In this calculation, assume that the unknown ancestor counts as a single mouse-bowler whose bowling average is the Universal Mouse Bowling Average Average, standardized by the Mad Scientists' Bowling League to be 50.
First define an extended mouse bowler tree definition that holds all the information a regular mouse bowler tree, plus for each known mouse the difference between its actual score and its predicted score (i.e., the average score of all of its ancestors). Then write the function mouse-tree->extended-mouse-tree, which extends the given mouse bowler tree with the new information.
Hint: decomposing this problem into appropriate helper functions is not trivial. Think carefully about the kinds of data each function will return and manipulate.
Part 4 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 highest number. It returns false if there are no mice in the given mouse bowler tree.
This lab is due on Friday, October 20th at 11:59PM. Please submit it by mailing it, along with your name and the name of your lab partner, to jacobm+lab@cs.uchicago.edu.
Jacob Matthews
jacobm at cs.uchicago.edu
Hinds 026