6.001 Quiz 1 Preparation Exercises
10 October 1996

   by Anthony Kam, with help from notes made by John Buck, Lynn Stein,
      Keith Swartz, and other past teachers of 6.001.

                    READ THIS FIRST!

These are some exercises to prepare you for Quiz 1, which will take
place in the evening of Oct 17.  These exercises are not comprehensive,
and they are meant to be diagnostic.  They are not a substitute for
normal studying!

In my personal opinion, the best way to study is to review the lecture
notes, supplemented by reading the book (try to find the time).  The
book is actually very well written and contains many subtle discussions.
Also, review the PS and the PS solutions -- sometimes even if you get a
good grade on the PS, the solution might still point out something
interesting.

Then, practise!  Find old quizzes, recitation miniquizzes (from Prof
Shavit or not), etc. and practise!  If you practise on a sample quiz, I
recommend that you time yourself -- if you're going to practise,
you might as well make it realistic.

I only have time to write exercises to cover these areas:

- substitution model
- orders of growth
- high-order procedures
- list handling procedures

Besides these, you also need to know about more basic things like 

- box and pointer diagrams (also "What will SCHEME print ...?" questions)
- the quotation mark and eq?
- data abstraction
- basic list procedures such as map, append, reverse and so on

However you should be able to easily find exercises on these more basic
things.  And you should practise those also!!!  The fact that they're
simpler / more basic makes it all the more important to get them right,
since most of the class will get them right!

These exercises are meant to be diagnostic, and so they should be tried
after you have studied the PSs and the notes.  Doing these exercises
will hopefully show you what area you are weak in, and so you can put
more effort in those areas.  I strongly suggest that you actually do all
of them, instead of just looking over them.

Once again, if you have any questions about any part of 6.001, please
dont hesitate to ask me.  The best way to reach me is to send email to
antkam@athena.mit.edu.  You can ask questions in email and I will
answer them in email.  You are also most welcome to schedule a time with
me, so we can meet in a comfortable place like the Student Center study
room, or you can come to my office hours (Tuesday 10/15 1-5pm Tutorial
area), and we can talk about 6.001.  To schedule a time, simply send me
email or talk to me after class.

Good luck and good skill.

Substitution Model

In each case below, use the substitution model to show (i.e. draw) what
happens, and also give the final value.  You can represent a procedure
value using a box figure like this (or draw whatever you like):

; example
(define (foo x y) (* 2 x y))
(foo 3 5)
=> ( +-----------------+   3   5 )
     | param: x y      |
     | body: (* 2 x y) |
     +-----------------+
=> (* 2 3 5)
;Value 30

; problem 1
(define x 5)
(define y 7)
(let ((x y)
      (y x))
  (+ x y))
; in the first step of your substitition, de-sugar the LET first
;Value: 

; problem 2
(define (compose f g) 
  (lambda (x) (f (g x))))
((compose (lambda (x) (* x x)) (lambda (y) (+ 2 y))) 7)
;Value:

; problem 3
(define (compare f g)
  (lambda (x) (- (f x) (g x))))
((compare (lambda (x) (* x x)) (lambda (y) (+ 2 y))) 7)

Orders of Growth

The first two definitions that follow below are the usual definitions of
append and the recursive version of reverse (called reverse-r here to
avoid confusion with an iterative version).  The third defintion is
similar to append (but how similar?)

(define (append l l2)
  (if (null? l)
      l2
      (cons (car l) (append (cdr l) l2))))

(define (reverse-r l)
  (if (null? l)
      nil
      (append (reverse-r (cdr l)) (list (car l)))))

(define (magic l l2)
  (if (null? l)
      (if (null? l2)
          l2
          (cons (car l2) (magic l (cdr l2))))
      (cons (car l)(magic (cdr l) l2))))

What is the time and space requirements on each procedure in terms of
the lengths of the input lists?  Note that in case of append and magic,
there are two input lengths -- that of l and that of l2, so you have to
specify how the time and space requirements depend on each, or both.

For space requirement, we're only interested in the space required to
keep track of the computation, in the sense of the actor model (or
substitution model).  We're not interested in the cons-cell space taken
up by the input lists nor new cons-cell space allocated for the output.

Finally, describe what the magic procedure does.  If you are correct,
you should find it very similar to append, in which case contrast the
difference(s) between them.

Finally, give the running time and space requirements of the following
procedures.  (Strictly speaking, for some problems it may be hard to
find both an upper bound and a lower bound -- which is what the theta()
notation implied.  In that case, just find an upper bound, which is what
the O() notation implied.)  Assume in all cases these functions are
called with n being positive integers.

(define (fib n)
  (if (< n 2)
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

(define (foo n)
  (cond ((<= n 1) 1)
        ((even? n) (+ (foo (/ n 2)) 1))
        (else      (foo (- n 1)))))

(define (fee n)    ; probably difficult
  (cond ((<= n 1) 1)
        ((even? n) (+ (fee (/ n 2)) (fee (/ n 2))))
        (else
         (let ((m (- n 1)))
          (+ (fee (/ m 2)) (fee (/ m 2)))))))

Higher Order Procedures

Consider the following summation procedure:

(define (sum a term b next)
  (if (> a b)
      0
      (+ (term a)
         (sum (next a) term b next))))

Use this procedure to write scheme expressions to calculate the
following summations.

  20
  ---  
  \    1
  /   ---
  ---  n
  n=1


  ---
  \
  /   (4*foo(n) - 6)    ; foo is some already defined function
  ---
 n=1,4,7,10

   8
  ---
  \      8!       ; ! stands for factorial, i.e. k! is factorial of k
  /   ---------   ; assume factorial is already defined
  --- n! (8-n)!
  n=0

  1     3     3     5     5     7
 --- + --- + --- + --- + --- + ---  ; the denominators are the squares
  4     4    16    16    36    36   ; of 2, 4 and 6

The pattern in sum (above) and product (covered in one of the tutorials)
can be captured using a high-order procedure, range-accum.  (This is
slightly different from the one in the book.)

(define (range-accum combiner null-value a proc b next comparison)
  (if (comparison a b)
      null-value
      (combiner (proc a)
                (range-accum combiner null-value (next a) proc b next 
                             comparison))))

Define sum and product using range-accum.

Also, how can you use range-accum to generate

- the list (1 3 5 7)?

- the list (9 8 7)?

- How about the list  ((1) (11) (111)) -- is that possible?

You have been given the compose function above.  You have also seen the
repeat function in class and/or PS2.  Remember that the function repeat
takes a one-argument function f and a non-negative integer n and returns
the one-argument function which applies f to its input n times.  Write
repeat USING compose.

(define (repeat f n)
  ...)

((repeat square 2) 3)
;Value: 81

In the style of PS2, the type of square is SchNum->SchNum.  If the type
of the input f to repeat is denoted T->T, what is the type of repeat?

Following are some scheme expressions that use repeat and compose in
various ways.  What would happen in each case?  (In case you dont know,
1+ is a one-argument scheme primitive procedure that adds 1 to its
argument, i.e., (1+ n) and (+ 1 n) are equivalent.)

(define (n-sq-f1 f n)                           ((n-sq-f1 1+ 2) 2) =>
  (lambda (x) (square ((repeat f n) x))))

(define (n-sq-f2 f n)                           ((n-sq-f2 1+ 2) 2) =>
  (repeat (lambda (x) (f (square x))) n))

(define (n-sq-f3 f n)                           ((n-sq-f3 1+ 2) 2) =>
  (repeat (lambda (x) (square (f x))) n))

(define (n-sq-f4 f n)                           ((n-sq-f4 1+ 2) 2) =>
  (lambda (x) ((repeat square n) (f x))))

(define (n-sq-f5 f n)                           ((n-sq-f5 1+ 2) 2) =>
  (lambda (x) (f ((repeat square n) x))))

(define (n-sq-f6 f n)                           ((n-sq-f6 1+ 2) 2) =>
  (compose (n-sq-f1 f n) (n-sq-f2 f n)))

(define (n-sq-f7 f n)                           ((n-sq-f7 1+ 2) 2) =>
  (repeat (compose n-sq-f3 f) n))               
                                                (n-sq-f7 1+ 2)     =>

Famous List Procedures - The Next Generation

The most famous and useful list procedures include map, length, append,
reverse.  Make sure you know them very well -- i.e. you know how they
can be implemented and what their time and space requirements are, and
you can use them with ease and in clever ways.  They should really form
an abstraction and become part of your basic repetoir of tools.

The famous list procedure filter takes in a predicate pred (a predicate
being a function that returns true or false), and a list l, and creates
a new list containing only those elements of l that satisfies the
predicate.  Write filter.  What is the time and space requirement of
your procedure?

(define (filter pred l)
  ...)

(filter odd? '(1 2 3 4 5 6 7 8))                 =>     (1 3 5 7)
(filter (lambda (x) (= (remainder 28 x) 0))
        '(1 2 3 4 5 6 7 8 9 10 11 12 13 14))     =>      (1 2 4 7 14)
(filter even? (filter odd? '(1 2 3 4)))          =>      ()     ; nil

You have just seen range-accum in the last section.  There are many
variations on the general idea of accumulating.  You will now write a
version of a famous high-order list procedure called accumulate, which
you have already seen in the book.

You might find it helpful to review the definitions of map, append and
the recursive version of reverse.  append and reverse are given before.
Here is the definition of map:

(define (map f l)
  (if (null? l)
      nil
      (cons (f (car l))  (map f (cdr l))  )))

Write a procedure accumulate that captures this common pattern in map,
append and reverse-r.  accumulate should take the following inputs: a
two-argument procedure called combiner, an initial value, and a list.
here is a definition of map in terms of accumulate:

(define (map f l)
   (accumulate (lambda (car-of-l rest)        ; combiner
                  (cons (f car-of-l) rest))
               nil     ; init-value
               l))

(define (accumulate combiner init l)
  ...)

Now, you should be able to define append and reverse-r in terms of
accumulate.

(define (append l l2)
  (accumulate ...))

(define (reverse-r l)
  (accumulate ...))

Now for a harder exercise, try to define filter in terms of accumulate.

(define (filter pred l)  ; might be hard
  (accumulate ...))

You have seen how the basic famous list procedures can be implemented
from cons, car, cdr, and also from specializing a high-order procedure
accumulate.  In class, you have also considered recursive and iterative
versions of these procedures and their time/space requirements.  (Note
that accumulate can only be used to define recursive versions of other
procedures.  (Why?)  Thus the iterative version of reverse cannot be
defined in terms of accumulate.)

Here is one more list procedure, in fact Exercise 2.36 in the book,
about accumulate-n which we talked about in tutorial (when we talked
about matrix tranpose).  Here is an example of this function at work.
Fill in the ... parts below in its definition.  You can obviously assume
that accumulate, map, append, filter, etc. are all already defined.

(define (accumulate-n op init seqs)   ; might be difficult
  (if (null? (car seqs))
      nil
      (cons (accumulate op init ...)
            (accumulate-n op init ...))))

(accumulate-n + 0 '((1 2 3) (4 5 6)))
; this computes a length-3 list:
;  (   (+ 1 (+ 4 0))   (+ 2 (+ 5 0))  (+ 3 (+ 6 0))  )

;Value: (5 7 9)

One final accumulating procedure.  accum-tree is like accumulate, but
acum-tree works on a tree (i.e. list of lists, recursively) instead.
So, accum-tree takes a combiner operator, an initial-value, and a tree,
and uses the combiner to combine all the leaf values (the non-pairs /
the atoms) of the tree with the initial-value.

First, as a warm-up, write accum-tree assuming that, in addition to
everything you've seen or written in this quiz review so far, you also
have the fringe (a.k.a deep-flatten) function discussed in tutorial.
(See exercise 2.28 in the book if you forgot what fringe does.)

(define (accum-tree op init tree)  ; using fringe
  ...)

(accum-tree + 0 '((1 (2)) 3 4 (5) ((6) 7)))    ; example A
; Value: 28

Now, the real challenge, write accum-tree without using (or defining
your own) fringe.

(define (accum-tree op init tree)  ; without fringe, might be difficult
  ...)

(accum-tree + 100 '((1 (2)) 3 4 (5) ((6) 7)))  ; example B
;Value: 128

If you are not careful, your accum-tree would work for example A above
but not for example B.  In that case you probably deserve 60% credit or
so.  

Also, if your accum-tree is careful enough to always combine elements in
a left-to-right order, then you can actually define fringe in terms of
accum-tree!  If you dont think it's possible, it's OK, since accum-tree
as specified above does not require it combine leaves in left-to-right
order.  However, if you think your accum-tree can do that, define fringe
in terms of it:

(define (fringe tree)        ; might not be possible for all definitions
  (accum-tree ... ... tree)) ; of accum-tree

The Last Question

The following problem appears in Quiz 1 of Fall 91.  In my opinion it is
one of the best problems ever written.  (If you plan to do that quiz in
a timed manner, skip this problem right now.)  

You're free to use the basic list functions map, length, append,
reverse, filter, etc..  (Not all of them will be useful.)  But do not
assume there is an accumulate or some other complicated list functions.

--- start of quiz question ---

Now that you've implemented filter...consider these three procedures:

       o filter-no-duplicates is like filter, except that each item
         appears at most once in the result list, regardless of how
         many times it appears in the input list.  The order of the
         elements in the resulting list does not matter.  For example:

         (filter-no-duplicates odd? '(1 2 1 3 4 5 5 6 7 8 5))

         could return (1 3 5 7) or (3 5 1 7), etc.

       o filter-tree takes two inputs--a predicate and a tree (that
         is, a list of lists).  Filter-tree returns the list of those
         atoms in the tree for which the predicate is true.  The order
         of the elements in the resulting list does not matter, but
         each element should appear in the list the same number of
         times as it appeared in the tree.  For example,

         (filter-tree odd? '(1 ((2 1) 3 4) 5 (((5) 6 7 8) 5)))

         could return (1 1 3 5 5 7 5) or (3 5 5 5 7 1 1), etc.

       o Filter-tree-no-duplicates is like filter-tree, except that
         each item appears at most once in the result list,
         regaredless of how many times it appears in the input list.
         For example, when called on the list above, it would return
         (1 3 5 7) or (3 5 7 1), etc.

For the remainder of this problem, you are to implement these three
procedures.  However, we do NOT want you to implement them independntly
as three separate, monolithic procedures.  Instead, we want you to
decide upon a couple of meaningful pieces from which these three
procedures can be implemented, then implement these pieces as
procedures, and then implement the three procedures in terms of these
pieces.  (You may also use filter as a piece without re-defining it.)
For each of the pieces that you implement, provide a clear specification
of what it is supposed to do (one or two sentences).

---- end of quiz question ---

In that quiz, several students misread the question and think they have
to implement a very general, very high-order procedure, from which
filter-no-duplicates, filter-tree, filter-tree-no-duplicates can be
defined.  (That function might as well be called
super-filter-maybe-duplicate-maybe-tree...!)  That would be a very
difficult thing to do, and it is NOT what the question is asking for.

This is essentially an engineering design problem.  You are supposed to
write several smaller, helper procedures that perform subtasks, document
them, and then build the three required procedures using these helpers.
You should try this problem.