recitation 14: trees & search

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

* any questions on the project?

* any questions from lecture?

* depth-first search

* breadth-first search

* best-first search

* beam search

* tree vs. graph

* directed graph

* memoization

* what's the purpose of *search-debug* in the project?

* draw the stylized graph diagram for test-cycle:

(define test-cycle
  (make-graph (list
   (make-graph-element 'a '(b c) '(words for node a))
   (make-graph-element 'b '(c) '(words for node b))
   (make-graph-element 'c '(a) '(words for node c)))))



---------------------------------------------------------------------------------------
(define my-tree (list 1 (list 2 3 (list 4 5)) (list (list 6))))

* draw the box & pointer diagram for my-tree


* how does my-tree print?
(1 (2 3 (4 5)) ((6)))

* draw a "stylized tree diagram" for my-tree


* how are they related?
Each node of the tree is a proper list in the box & pointer diagram.
If the list has n elements, the node has n branches.


(define (leaf? tree) (not (pair? tree)))

(define (tree-manip leaf-op init merge tree)
  (if (null? tree)
      init
      (if (leaf? tree)
	  (leaf-op tree)
	  (merge (tree-manip leaf-op init merge (car tree))
		 (tree-manip leaf-op init merge (cdr tree))))))

* type of tree-manip: A->B, B, (B,B->B), tree<A> -> B

* use tree manip to square every element of a tree

  (square-tree my-tree)  =>  (1 (4 9 (16 25)) ((36)))

  (define (square-tree tree)
    (tree-manip square nil cons tree))

* use tree-manip to compute the product of all the even-valued 
  leaves of the tree 

  (product-even my-tree)   =>  48

  (define (product-even tree)
    (tree-manip (lambda (x) (if (odd? x) 1 x)) 1 * tree))

* use tree-manip flatten a tree

  (flatten my-tree)   =>   (1 2 3 4 5 6)

  (define (flatten tree)
    (tree-manip (lambda (x) (list x)) nil append tree))

* use tree-manip to "deep-reverse" a tree (reverse the order of
  children at each node)

  (deep-reverse my-tree)  =>  (((6)) ((5 4) 3 2) 1)

  (define (deep-reverse tree)
    (tree-manip 
     (lambda (x) x) 
     nil 
     (lambda (x y) (append y (list x)))
     tree))

* use tree-manip to sum up the values of the leaves of the tree

  (sum-leaves my-tree)  =>  21

  (define (sum-leaves tree) 
    (tree-manip (lambda (x) x) 0 + tree))

* use tree-manip to create a new tree, which keeps the odd-valued
  leaves of the original tree within the same tree structure, but
  removes even valued leaves

  (keep-odd-leaves my-tree) =>  (1 (3 (5)))
  (keep-odd-leaves (list 1 2 3 4 5 6))  =>  (1 3 5)
  (keep-odd-leaves (list 2 4 6))  =>  nil
  (keep-odd-leaves (list (list 1) (list 4) (list 6))) =>  ((1))

  (define (keep-odd-leaves tree) 
    (tree-manip 
     (lambda (x) (if (even? x) nil x))
     nil
     (lambda (x y) (if (null? x) y (cons x y)))
     tree))

* for each of the above exercises, write down the types of arguments &
  return value for the calls to tree-manip

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