# 1997 F

*215,811*pages on

this wiki

## Ad blocker interference detected!

### Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

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.