Lesson Plan - 6.001 SP04 - recitation 6

HOPs, programming methods

announcements:

Quiz 1 will be held on Tuesday, March 2 from 7:30 pm to 9:30 pm.

    * Students with last names beginning with A through D will take the exam in 4-270
    * Students with last names E through Z will take the exam in Walker Memorial 50-340.
    * If you have a conflict with this exam time, please email boning@mit.edu as soon as possible, and absolutely no later than Thursday, February 26. 

problems

(define (class-numbers sched)
  (map get-class-number sched))

(define (drop-class sched classnum)
  (filter (lambda (class) (not (= (get-class-number class) classnum)))
          sched))

(define (total-scheduled-units sched)
  (fold-right 0 + (map get-class-total-units sched)))

(define (credit-limit sched limit)
  (fold-right
   (empty-schedule)
   (lambda (class sched)
     (if (< (total-scheduled-units (add-class class sched)) limit)
         (add-class class sched)
         sched))
   sched))

slick solution: (O(n), not O(n^2))
(define (credit-limit sched limit)
  (car
   (fold-right
    (list (empty-schedule) 0)
    (lambda (class sched)
     (if (< (+ (get-class-total-units class) (cadr sched)) limit)
         (list (add-class class (car sched))
               (+ (get-class-total-units class) (cadr sched)))
         sched))
    sched)))


(define (make-node val left right)
  (lambda (p)
    (p val left right)))

(define (get-val node)
  (node (lambda (val left right) val)))

(define (get-left node)
  (node (lambda (val left right) left)))

(define (get-right node)
  (node (lambda (val left right) right)))

(define (node->list node)
  (node (lambda (val left right)
	  (list val
		(if left (node->list left) left)
		(if right (node->list right) right)))))

(define (new-right node right)
  (node (lambda (val left oldright) (lambda (p) (p val left right)))))

(define (new-left node left)
  (node (lambda (val oldleft right) (lambda (p) (p val left right)))))

(define (insert-tree val tree)
  (cond ((not tree)
	 (make-node val #f #f))
	((< val (get-val tree))
	 (new-left tree (insert-tree val (get-left tree))))
	(else
	 (new-right tree (insert-tree val (get-right tree))))))

(define (in-order-read tree)
  (cond ((not tree)
	 nil)
	(else
	 (append (in-order-read (get-left tree))
		 (list (get-val tree))
		 (in-order-read (get-right tree))))))


(define (mysort lst)
  (in-order-read (fold-right insert-tree #f lst)))

(define (leaf? node)
  (node (lambda (val left right) (and (not left) (not right)))))


(define (tree-accum op leafop tree)
  (cond ((not tree) #f)
	((leaf? tree)
	 (leafop (get-val tree)))
	(else
	 (op (get-val tree)
	     (tree-accum op leafop (get-left tree))
	     (tree-accum op leafop (get-right tree))))))

(tree-accum (lambda (v l r) l (append l (list v) r))
	    list
	    (fold-right insert-tree #f '(3 7 5 8)))