Week 8 Set b

Due Date Thursday 10/25 at 9:00pm (Week 8)

Purpose To practice designing functions over trees, mutually recursive data, and two complex inputs.

Finger Exercises

Exercise 1 From HTDP, 310 311 312 313

Graded Exercises

Tree Maps

We have now seen both maps and trees. While we’ve combined these concepts in lecture, you will now add a layer of abstraction through parametric data types in this assignment.

Exercise 2 Develop a data definition, including examples and a template, of a [TreeMap X Y]. It should contain a [Comparison X] as well as a binary search tree of pairs, which contains an X and a Y value (referred to as a key and an info, respectively) at each node.

For this assignment, a [Comparison X] is a [X X -> Real], where a negative output indicates the first parameter comes before the second, a positive output indicates the first parameter comes after the second, and 0 indicates they are equal.

Note than an empty treemap is possible.

In your treemap examples, and as you test the below functions, you should have two trees which operate over the same types of keys which demonstrate how binary search tree behaviors can differ when given a different comparison function.

Exercise 3 Design a function insert, which given a key and an info (with types X and Y, respectively) inserts the pair into a treemap. If the key is already present, the old value should be overwritten. Be sure to uphold the invariants of a binary search tree.

Exercise 4 Design a function find, which given a key finds the associated info in the tree. Don’t search any more of the tree than necessary, and error if no such key is found.

Exercise 5 Design a function submap, which given two keys, lo and hi, and a treemap, outputs a treemap where the binary search tree is a subtree of the original, containing no keys lower than lo or higher than hi (as indicated by the comparison function).

S-Expressions

While you do not have to provide examples or a template for s-expressions, you may find them helpful.

Exercise 6 Design the function topsy-turvy, which inverts the order of an s-expression. An inverted s expression should not only have the orders of its list reversed, but each individual element of the list should also be inverted. Note the symbols themselves should be left as-is.

Exercise 7 Design the function find-path, which given an s-expression and a symbol outputs the path to the leftmost occurence of that symbol in the s-expression. If that symbol is not present, the function should output #false. As an example, the path to 'wish in 'wish would be '(), and in '(though (i might (wish))) would be '(1 2 0).