recitation 8: more practice problems...

quiz on wednesday 7:30-9:30.  see course web page for room location.
covers all material, except tuesday's lecture (3/1) and psets/projects
you haven't turned in yet.  see web page for quiz reviews (sun & mon)

* 1 8.5x11 sheet of notes, handwritten/printed/photocopied
* read each question carefully
* don't spend too long on any one problem
* don't leave anything blank, we will give partial credit
* be concise & choose good variable names
  - your answer should fit in the box provided
* don't get an abstraction violation stamp!

------------------------------------------------------------
Let's implement a "queue" data abstraction.  A queue stores a
collection of elements which will be accessed/used/processed in FIFO
order (first-in-first-out).  Thus, the first element enqueued is also
the first element dequeued.

(head (enqueue 5 (empty-queue)))  => 5
(define q (enqueue 4 (enqueue 5 (enqueue 6 (empty-queue)))))
(head q) =>  6
(head (dequeue q))  =>  5

* Decide on an implementation for queues, then draw a box-and-pointer
  represention of the value of q as defined above.






* Write (empty-queue).  What's the order of growth in time & space?





* Write (enqueue x q) that returns a new queue with the element added
  to the tail.  What's the order of growth in time & space?





* Write (dequeue q) a procedure that returns a new queue with the head
  element removed.  What's the order of growth in time & space?




* Write (head q) that returns the value of the head element.  
  What's the order of growth in time & space?




------------------------------------------------------------ 
Cute Trick:  what's this do?

(define (cons a b) (lambda (x) (if x a b)))
(define (car p) (p #t))
(define (cdr p) (p #f))

It's a way to implement the pair abstraction using procedures.

------------------------------------------------------------
Consider a procedure (head n lst) that returns the first n elements of
lst, and another procedure (tail n lst) that returns the last n
elements of lst.  Here are definitions of head and tail:

(define (head n lst)
  (if (= n 0)
      nil
      (cons (car lst)
            (head (- n 1) (cdr lst)))))

(define (tail n lst)
  (if (= (length lst) n)
      lst
      (tail n (cdr lst))))

* What is the result of evaluating (head 5 '(1 2 3))?
Error: cannot take the car/car of nil (or something similar)

* Is head recursive or iterative?  
recursive

* Is tail recursive or iterative?
iterative

* What are the time and space growth of head?  
O(n) space & time, where n is the size of input n.

* What are the time and space growth of tail?
O(1) space & O(m*(m-n))time, where n is the size of input n 
and m is the length of lst.  Remember that the procedure length
implemented iteratively requires O(1) space and O(n) time.

------------------------------------------------------------ 
Let's write merge-sort!  The basic idea is to cut the problem in half,
sort each half then combine the results of the half problems.  This
common pattern in algorithm design is also called divide and conquer.

* Write the procedure split that takes in one list and returns a two
  lists of approximately equal size.  (How do we return two things??)
  What's the order of growth in time & space?	

(define (split lst)
  (if (null? lst) 
      (list nil nil)
      (let ((tmp (split (cdr lst))))
	(list (cons (car lst) (cadr tmp))
	      (car tmp)))))

(split (list 1 2 3 4 5 6 7 8 9)) => ((1 3 5 7 9) (2 4 6 8))

time: O(n)
space: O(n), this could also be written iteratively

* Write the procedure merge that takes in two sorted lists and returns a 
  sorted list.  What's the order of growth in time & space?

(define (merge a b)
  (cond ((null? a) b)
	((null? b) a)
	((> (car a) (car b))
	 (cons (car b) (merge a (cdr b))))
	(else
	 (cons (car a) (merge (cdr a) b)))))

(merge (list 1 3 5 7 9) (list 2 4 6 8)) => (1 2 3 4 5 6 7 8 9)

(merge (list 1 2 3 4) (list 5 6 7 8)) => (1 2 3 4 5 6 7 8)

(merge (list 1 2 7 8) (list 3 4 5 6)) => (1 2 3 4 5 6 7 8)

time: O(n)
space: O(n), this could also be written iteratively

* Now we can write merge-sort.  What's the order of growth in time & space?

(define (merge-sort lst)
  (if (or (null? lst) (null? (cdr lst)))
      lst
      (let ((sublsts (split lst)))
	(merge (merge-sort (car sublsts))
	       (merge-sort (cadr sublsts))))))

(merge-sort (list 3 9 5 1 2 6 4 8 7)) => (1 2 3 4 5 6 7 8 9)

time: O(n log n)
space: O(n), this could also be written iteratively

------------------------------------------------------------