1997 F

213,091pages on
this wiki
Add New Page
Add New Page Discuss this page0

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

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).
(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 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.

Also on Fandom

Random wikia