# 1997 F

224,605pages on
this wiki

2. (15%) Consider the following algorithm for finding the k-th smallest one of a set S of n elements.

Select(k,S)
Step 1: Divide S into $\lceil n/5 \rceil$, each consists of 5 elements.
Step 2: Sort each subset of elements.
Step 3: Find the element p which is the median of medians of the $\lceil n/5 \rceil$ subsets.
Step 4: Partition S into $S_1, S_2, and S_3$ which contain the elements less than, equal to, and greater than p, respectively.
Step 5: If |$S_1$|≥k, Select(k,$S_1$);
else if |$S_1$|+|$S_2$|≥k, return p;
otherwise, Select(k-|$S_1$|+|$S_2$|, $S_3$).
(a) (5%) Let T(n) be the time complexity of the above algorithm. Write a recurrence of T(n).
(c) (5%) What is the asymptotic solution of T(n) (in big-O notation). You do not need to prove your answer.

3. (10%) Consider the following sorting algorithms. (a)Heap sort, (b)Insertion sort, (c)Quick sort, (d)Merge sort, (e)Radix sort on integers smaller than n, (f)Radix sort on integers smaller than $n^3$, and (g)Bubble sort

(1) (5%) What is the worst-case time complexities of the above algorithms?
(2) (5%) Which of the above algorithms are stable?
(3) (5%) Give a simple scheme to make all the above algorithms stable. Your scheme should not increase the time complexities.

4. (10%) Show that $\sum_{k=1}^{n} \frac{1}{k^2}$ is bounded above by a constant.

5. (10%) Show that $\sum_{k=1}^{n} \frac{1}{k}$ is divergent (i.e., it cannot be bounded above by a constant.)

6. (10%) Let A[1..n] be an array of n distinct values. The rank of a value x in A is the number elements in A that are not greater than x. The rank finding problem is to compute for every element A[i] 1≤i≤n, its rank in A. For example, letting n=3 and A[1..n]=(4,3,6), the output should be(2,1,3). Implement a rank finding algorithm based upon the divide-and-conquer approach.

7. (20%) Let T be the minimum spanning tree found by Prim's algorithm in an undirected, connected graph G.

(a) (5%) Prove that T contains all edges of shortest length in G unless such edges induced a cycle.
(b) (5%) Prove that if e*=(a,b) is an edge of G not in T and if P is the unique path in T from a to b, then for every edge e in P, the length of e is not greater than that of e*.
(c) (10%) Prove that if all edges in G have different lengths, then the minimum spanning tree of G is unique.

8. (10%) Using the dynamic programming approach to find the longest path in a directed acyclic graph. Use the following graph as an example to explain your algorithm.