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:
- [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:
- (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).
- (tree-reverse <tree>) I.e. switches the order of all the
children in the tree.
- (deep-map list) I.e. like map, but deep.
- (deep-filter list) I.e. like filter, but deep.
- (tree-map node)
- (tree-filter) this one could be difficult. Just make wise
decisions.
- [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.]
- [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)
- [Easier] (get-all-data tree) Similar to (3). Returns a [flat] list of all
of the ‘datums’ contained in the tree.
- [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)).
- [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))).
- [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:
- 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:
- [Easy] At least one decent constructor for each shape (e.g. Line needs
two endpoints, Triangle needs three points, Rectangle needs two opposite
points.)
- [Easy] Selectors for each shape (to get each of the original points
back)
- [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.
- [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).
- [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.]