Some Final Review Questions, Part I [I may post a part II on my webpage later on.]

 

Note: I have indicated the approximate level of difficulty by each problem. By final exam time, you should be very good at [easier]-level problems, and [medium]-level questions should make you think a bit but should be doable. If you can do [harder]-level problems easily, you are probably well-prepared on the associated topics. As usual, this is not an exhaustive or comprehensive list of topics that may appear on the exam.

 

List, Tree, and Nasty Recursions:

  1. [Easier] Port some of the old sentence-recursions to lists and (if they make sense) to trees. Your list implementations should do either 1-level recursion or deep-recursion. E.g. you should be able to do stuff like:
    1. (deep-list-reverse <list>) E.g. (deep-list-reverse ‘(1 2 (3 4 5 (6) (7 8)) 9)) è (9 ((8 7) (6) 5 4 3) 2 1).
    2. (tree-reverse <tree>) I.e. switches the order of all the children in the tree.
    3. (deep-map list) I.e. like map, but deep.
    4. (deep-filter list) I.e. like filter, but deep.
    5. (tree-map node)
    6. (tree-filter) this one could be difficult. Just make wise decisions.
  2. [Medium] (cp lst-of-lists) Takes a list of lists, and returns a list of all of the possible ways [in any order] of choosing exactly one element from each of the original lists. E.g. (cp ‘((Tom Mary Sue) (eats likes loves) (apples oranges bananas)) è ((Tom eats apples) (Tom eats oranges) (Tom eats bananas) (Tom likes apples) … (Mary likes apples) … (Mary loves apples) … (Sue loves oranges) (Sue loves bananas)). [In this example, there should be 27 possibilities.]
  3. [Easier] (ltc list) Takes a [possibly deep] list and returns all of the elements of the list ‘squashed’ into a flat list [in any order]. E.g. (tc ‘(1 (((2))) 3 (4 5 (6) (7 8)) 9)) è (1 2 3 4 5 6 7 8 9)
  4. [Easier] (get-all-data tree) Similar to (3). Returns a [flat] list of all of the ‘datums’ contained in the tree.
  5. [Harder] (permutations <list>) Returns a list of all of the permutations [in any order] of the original list. E.g. (permutations ‘(1 2 3)) è ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).
  6. [Easier, if your in my sections; Medium otherwise] Make sure that you can write and understand the (list-alternate start func list) and (tree-alternate start func list) procedures we did in section. E.g. (list-alternate #t double ‘(1 2 3 ( 1 2 3 ( 1 2 3 (1 2 3))))) è (2 4 6 (1 2 3 ( 2 4 6 ( 1 2 3)))); (list-alternate #f double ‘(1 2 3 ( 1 2 3 ( 1 2 3)))) è (1 2 3 ( 2 4 6 ( 1 2 3))).
  7. [Harder] Don’t like MacGambit? Here’s your chance to make a new one. Write a procedure (eval list) that returns the result of treating list as if it were expression and evaluating it. E.g. (eval ‘(+ (* 2 3) (- 9 8))) è 7. You can assume that we have written a proc (apply func <list-of-args>)) that will return the result of applying that func to that list of simple args. E.g. (apply + ‘( 1 2 3)) è 6. Note that (apply + ‘((1 0) 2 3)) will NOT work – apply requires that you use arguments that have already been evaluated (hint, hint).

Abstraction and Graphics:

  1. Build on the graphics-lib.scm library by adding on a few new shapes. You should define an interface (constructors and selectors) and a decent implementation for each of these shapes: Line, Triangle, Rectangle. You should implement the following:
    1. [Easy] At least one decent constructor for each shape (e.g. Line needs two endpoints, Triangle needs three points, Rectangle needs two opposite points.)
    2. [Easy] Selectors for each shape (to get each of the original points back)
    3. [Medium] (draw-<shape> <shape>) to actually draw the object. E.g. (draw-triangle <some triangle>), (draw-square <some-square>) etc. (draw-triangle (make-triangle X Y Z)) should draw the triangle on the screen.
    4. [Medium] (get-type <some shape>) returns triangle if <some shape> is a triangle, square if it is a square etc. Hint: It will help to store the type of the shape in the shape itself (and then get-type looks in that location to see what type of shape it is).
    5. [Trickier] A generalized get-draw-proc selector that gets a built-in draw procedure for each shape. E.g. ((get-draw-proc (make-square X Y))) will draw that square to the screen. I.e. instead of having to first check the type of the shape and call a special draw for each shape, when the shape is constructed, it makes its own draw proc (suited to its points) and stores that someplace that can be found by get-draw-proc. [Use part d as a starting point.]