Introduction to Algorithms and Data Structures, Fall 2004, Episode 5

Lecture, September 27

Subject : Recursion, induction, recurrences. Binary trees.

Text : Handout on Recursion. CLRS chap. 4.1-3 pp. 62—75, Chap. Appendix B.4-B.5 pp. 1080-1090, Chap 4.1-2 pp. 62-72, Chap. 10.4 pp. 214-216, and Chap. 12.1-2. pp. 253-262. You may want to read the second handout Recurrent problems after the lecture.

Prerequisites : understanding of big-O notation, log n, definition of mathematical induction (the use will be exemplified during the lecture), basics of rooted trees (CLRS app. B5). Also it will be convenient to remember how Quicksort and Merge-Sort work.

Comments : Note that this is an exceptionally difficult episode. Try to do your best to prepare yourself. Start with skim-reading the handout on recursion. If you are unfamiliar with the recursion and induction principles, then read the handout thoroughly. We will not cover all details in the lecture, but it will greatly help you in the entire course. You are welcome to contact the teachers, if you need more explanation. Read the remaining material after you are comfortable with the handout.

There is a supplementary handout titled Recurrent Problems, which can be read after the lecture. This handout contains an alternative, perhaps more enjoyable, presentation of material on solving recurrences, as well as a wealth of additional exercises (some of them very difficult). We only recommend the second handout for advanced students, as it requires somewhat higher mathematical maturity.

Warning : If you had downloaded a note on recursion linked here before September 20, then please discard it. We are not using it in the course this year.

Time : Monday, September 27, 9:00–12:00 (3×45min), Room 2A12

Tutorial : 13:00–16:00 (3×45min), Room 2A12

Assignments

(H) Use mathematical induction to show correctness of the formula for sum of the first n elements of geometric series (CLRS equation A.5 p. 1060).
Show by induction that a complete binary tree with height h has size 2^(h+1)-1.
Show that a complete binary tree with n nodes has height O(log n).
Let T(n)=T(n-1) + 2n and T(1)=2. Give an open formula for T(n) and prove by induction that it is correct.
Let T(1)=0 and T(n)=2T(n/2) + 1. Suppose that n is a power of two. Show by induction that T(n)=n-1.
(M) Let T(1)=0 and T(n) = T(n/2) + 1. Suppose that n is a power of two. Show by induction that T(n)=log n, where log is the logarithm with base 2.
CLRS 4.2-2 p. 72
CLRS 4.3-1, 4.3-2 p. 75
(M) CLRS 4.3-3 p. 75
(H) Write (in pseudo code) procedures Preorder-Tree-Walk, and Postorder-Tree-Walk. Compare all three implementations of tree traversals and note the differences. What changes?
(H) Write (in pseudo code) procedure Tree-Maximum.
(M) Write (in pseudocode) a procedure Count-Leaves returning the number of leaves in a given binary tree. Alternatively hand-in your solution to programming assignment 5.2f

The mandatory assignments should be handed in no later than October 8, at 13.00.

Programming Assignments

Assignment 5.1

Files ruler.mp and star.mp contain implementations of fractal ruler and fractal star from the handout on Recursion, written in the METAPOST language. The comment on top of each file explains how you can execute the program to obtain a drawing in PostScript. You may want to experiment with parameters in order to change the shape drawn. In particular you may want to change the value of granularity in the comparison in line 34 of star.mp file. On my machine the program becomes slow for granularity of 0.2mm. Experiment with a range of values and note down the execution times (time command on Unixes is useful for this purpose). Draw a graph and guess what kind of function the asymptotic complexity is? Can you reach this result theoretically? (Hint: Assume that drawing a single rectangle takes always the same constant time, regardless of the size. Write a recurrence defining time complexity solve it and show what is the asymptotic running time of the algorithm.)

Assignment 5.2

A binary tree can be implemented in Java as follows:

class BinaryTree { 

     public BinaryTree left, right;   

     public int label;

     

     public BinaryTree(int l) {

          left=right=null;

          label=l;

     }

     public BinaryTree(BinaryTree ltree,BinaryTree rtree, int l) {

          left=ltree;

          right=rtree;

          label=l;

     }

}

The left (right) field contains the BinaryTree object of the respectively left and right subtree. The nil value denotes that there is no given subtree in a given node. In particular for any leaf node leaf it should be the case that leaf.left==leaf.right==nil.

Construct in memory the tree presented on Fig. 12.1a in CLRS p. 254.
Write a recursive procedure int sumlabels(BinaryTree t) that computes a sum of all labels in tree t.
The height of the tree is defined in CLRS app. B5, p.1088. Height can be compute using the following recursive property (*): The height of the leaf node is 0. The height of an internal node in the tree is the greater of the two heights of the subtrees increased by 1. Use this recursive property to implement a method int height(BinaryTree t), computing height of tree t.
Show that your implementation of height runs in time linear in the size of the tree (size of the tree is the number of its nodes). If your implementation runs in the time exponential in the size of the tree, then better improve it!
Use mathematical induction to prove that property (*) does indeed hold for height of any rooted tree.
Write a method int CountLeaves(BinaryTree t) that computes the number of leaves in tree t.
Write a recursive method BinaryTree RandomBinaryTree(int h) that produces a randomly shaped binary tree of depth h with random labels.
Write a method CompleteBinaryTree(int h), which produces a complete binary tree of depth h with random labels. You can use RandomBinaryTree and CompleteBinaryTree to test your other functions. Can you estimate (theoretically) what is the maximum depth of a complete binary tree, which can still fit in the main memory of your PC?
Write a method InOrder which given a binary tree t produces a list (or array) containing the labels of tree nodes in the preorder traversal sequence.

Observe that in the pattern-speak, tree traversals are often somewhat silly referred to as the visitor pattern.