Please note: THESE ARE SAMPLE PROBLEMS. They are meant to be helpful, but they are neither guarenteed to cover all of the types of questions that will be included nor suggest the relative weighting of types of questions on the test. I believe that success on these problems will correlate well with success on the exam, but please remember the definition of a statistician (someone who drowned in a river with an average depth of 3 feet).

1.  3-trees have exactly 0 or 3 children per node.  Write the 
    axioms for the following functions:

    seed:  n --> T
    build: T,T,T  --> T
    left,center,right:  T --> T
    value: T --> n


    BTW, where are the values stored in this tree?



2.    Design an algorithm, which takes a graph, the names of two
      nodes in that graph and an integer, and determines whether 
      there is a path (between those two nodes) of weight less than
      the integer {you may use any algorithm we discussed in class
      as long as you clearly identify its parameters and effect}.


3.    Do an inorder traversal of a Binary Search Tree, as each node
      is traversed, add the node to an (initially) empty heap-ordered 
      tree.  What happens?


4.    Design an algorithm which reads a string of parenthesis, and 
      determines whether they are correctly matching.

5.    Describe a recursive function for converting a string of digits
      (e.g. "37249") into the integer (i.e. 37,249) it represents.

6.    Write an algorithm which merges two heaps into a single heap.
      What is the efficiency of your algorithm?