6.001/Recitation 16

Rob Speer

Since they're not posting the lecture notes online, this recitation's going to be a lot of miscellaneous crap.

Practicing the environment model

You should soon be able to just read an environment diagram right off the code. Here are some examples to try it on.

(define (fact n)
  (define (helper i prod)
    (if (> i n) prod
        (helper (+ i 1) (* prod i))))
  (helper 1 1))

(fact 4)

Another one:

(define curry-add
  (λ (a)
    (λ (b)
      (+ a b))))

((curry-add 3) 5)
((curry-add 4) 2)

Here's a harder one:

(define (memoize proc)
  (let ((memo ()))
    (λ (arg)
      (cond
        ((assoc memo arg) => cadr)          ; freaky syntax that does what you want
        (else
         (let ((newval (proc arg)))
           (set! memo (cons (list arg newval) memo))
           newval))))))

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

(define good-fib (memoize crappy-fib))

(good-fib 4)

And now for something completely different: search

Depth-first search

• Store paths in a stack
• Next path to search from is the most recent on the stack

Breadth-first search

• Store paths in a queue
• Next path to search from is the oldest on the queue

Shortest-first search

• Store paths in a priority queue
• Next path to search is the shortest path on the queue
• Only expand nodes once

Hill-climbing search

• Requires a distance estimate
• Store paths in a priority queue
• Next path to search is the one with the best distance estimate

A* search

• Requires a permissible distance estimate (never underestimates distance to the goal, only overestimates)
• Store paths in a priority queue
• Next path to search is the one with the best sum of its length so far and its distance estimate
• You get to only expand nodes once if you never underestimate the distance to any node
• A* is optimal