CSE 326, Spring 1998: Homework 3

Due 4/17/98

When asked to design an algorithm please provide the pseudocode with enough explanation that it can be understood easily.

1. (15 points) Consider the following general recurrence T(1) <= d and T(n) <= aT(n/b) + cn for a time bound. Show that:
   • If a < b then T(n) = O(n).
   • If a = b then T(n) = O(n log n).
   • If a > b then T(n) = O(n^{log_b a}) (n to the power log base b of a).
   You may assume that n is a power of b in your argument. A very good argument would determine the constants and low order terms hidden in the big O notation, and show the bound by induction on n.
2. (15 points) It is often handy to store a tree in a file. Assume each node in the tree contains an alphabetic character. In this case we may store a tree by inserting parentheses appropriately while doing a preorder traversal. The general idea is that a node is followed by the list of its children surrounded by parentheses. For example:

                              
                                 a
                               / | \
                              b  c  d
                             /    / | \
                            e    f  g  h
   

   is stored as the file "a ( b ( e ) c d ( f g h ) )" where spaces indicate newlines. We call this the preorder file format.
   • Design an algorithm which outputs the preorder file format of a tree given a pointer to the root of the tree. Assume the tree has nodes with fields "data", "first_child", and "next_sibling".
   • Design another algorithm which takes a preorder file format of a tree and produces the tree. You can assume there is an end of file marker at the end of the file. This algorithm can be done rather elegantly using recursion.
   • Is there a similar file format based on postorder traversal? If not why not. If so, then explain how to modify the algorithm for producing the tree from the preorder file format to an algorithm for producing the tree from the postorder file format.