CS252- Winter 2003- Assignment 1

Second assignment--CS252--Winter 2003

Date: February 4, 2003.
Due: February 11, 2003, 2:30pm.

Question 1	Drawing trees. An hv-drawing (h=horizontal, v=vertical) of a binary tree is such that for every node u, a child of u is either vertically below u or horizontally to the right of u, and the smallest rectangles covering the subtrees of u do not intersect. Give an O(n) worst-case time algorithm for drawing any binary tree with all n nodes at integer coordinates in the plane such that the covering rectangle has horizontal width at most n, and vertical drop at most log_2 n.
Question 2	Lower bounds. Compute an information-theoretic lower bound for sorting n elements in a comparison-based model when only k different values occur among the n elements. Tied elements can be sorted in any way. Simplify the bound as much as possible as a function of n and k. (Example: in sorting, the asymptotic bound n log_2 n is preferred over the bound log_2 (n!).) The bound should hold no matter how many elements are tied for each of the k values.
Question 3	Partial sum data structure. We wish to maintain a data structure that enables us to work with partial sums very efficiently. Let T[1],...,T[n] be n integers in a table. We define the k-th partial sum S_k = sum_{i=1}^k T[i]. The operations we wish to perform efficiently are: Initialize an all zero table. (This takes time n, so do not worry about this.) Update entry i to x (T[i] <- x). Find the value of S_k. Assume that integer addition is available at unit cost. Furthermore, n is fixed and known beforehand, so it is possible (but not necessary) to use arrays. After the initialization, assume that users may specify any sequence of updates and finds in any order, with any values of i, k and x imaginable. We are interested in the worst-case times of update and find. There are many possible solutions, but the simpler and the more efficient, the better! Discuss the complexity.
Question 4	Algorithm design. Write a simple non-recursive linear time algorithm for computing for each node in a binary tree the size of its subtree, assuming a RAM computational model.