# 1997 F

*229,977*pages 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 , 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 subsets.
- Step 4: Partition S into which contain the elements less than, equal to, and greater than p, respectively.
- Step 5: If ||≥k, Select(k,);
- else if ||+||≥k, return p;
- otherwise, Select(k-||+||, ).

- (a) (5%) Let T(n) be the time complexity of the above algorithm. Write a recurrence of T(n).
- (b) (5%) Justify your answer of (1).
- (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 , 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 is bounded above by a constant.

5. (10%) Show that 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.