NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Analysis of Algorithms Qualifying Examination
January 12th, 1999 -- 9-11am

Notes: 1) This is a closed-book test. 2) Please keep your answers brief and to the point. When you are asked to design algorithms, do not write programs. Developing all the algorithmic ideas needed and describing them is enough to fetch full points. Do not go to the extent of declaring variables and arrays and writing programs.

1.

(30 points) Consider an n-node binary tree (we do not distinguish between internal nodes and leaf nodes). Suppose that the nodes of the tree are numbered using integers $1,\ldots,n$. Given the pre-order and post-order traversals of the binary tree, your task is to compute the tree itself.

(a)

Suppose n=8 and the pre-order traversal is $1\;2\;4\;5\;7\;3\;6\;8$ and the post-order traversal is $4\;7\;5\;2\;8\;6\;3\;1$. Construct the corresponding binary tree.

(b)

Design an algorithm that takes pre-order and post-order traversals as input and constructs the corresponding binary tree. You can assume that the traversals are represented using arrays of size n. Your algorithm should run in $O(n\log n)$ time.

You will get partial points if you construct a correct algorithm that is slower.

2.

(35 points) You are given n numbers $x_1, x_2, \ldots, x_n$. For a pair of numbers x_i and x_j, the distance between them is given by d_ij=|x_i-x_j|. For the given n numbers, there are $\frac{n(n-1)}{2}$ such distances. Give an algorithm that computes the smallest n distances in $O(n\log n)$ time.
(Hint: Heaps might be useful.)

3.

(35 points) The partitioning problem is defined as follows: Given n integers, is there a way to partition the integers into two disjoint subsets so that the sums of the integers in each of the two subsets are equal? Formally, given integers $x_1,\ldots,x_n$, is there a subset S of $\{1,2,\ldots,n\}$ such that

$$\sum_{i\in S}x_i=\sum_{i\notin S}x_i?$$

Give a dynamic programming algorithm for this problem and compute its running time. Your algorithm need not necessarily run in polynomial time.