# 2006 S

221,769pages on
this wiki

1. (15%)

(a) Write a C-like procedure MAX2, which use (3/2)n - 2 comparisons to find the largest two numbers in a set of n distinct integers. Assume n elements are stored in an array.
(b) Prove (3/2)n - 2 comparisons are used in the procedure.

Ans: (a)

int i, Max1 = MAX(A[0], A[1]), Max2 = MIN(A[0], A[1]);
for ( i = 2; i < n; ++i )
if ( A[i] > A[i+1] )
if ( A[i+1] > Max1 )
Max2 = A[i+1], Max1 = A[i];
else if ( A[i] > Max1 )
Max2 = Max1, Max1 = A[i];
else
Max2 = A[i];
else
symmetry...

(b) Every loop choose one pair elements, every pair use three compariso, the loop excute n-2 time, there is one addition comparison in the beginning, so the complexity is (3/2)(n-2) + 1 = (3/2)*n – 2

2. (15%)

Set L={0}. So L is the language consisting only of a single element. Prove P=NP⇔L is NP-Complete.

Ans: L is NP, if input contains only one 0, we accept, otherwise reject, L is in P = NP. L is NP-Hard, we use SAT reduce to L, for any SAT instance, we can use polynomial time algorithm to compute its answer, if its answer is yes, we transform to 0, otherwise 1, this transformation is polynomial time, because P = NP. Then use L to decide 0 or 1. We can easily prove when SAT’s answer is yes iff L answer yes.

3. (15%)

Give an asymptotically tight bound for T(n) in each of the following recurrences. Please justify your answers.
(a) (5%) T(n)=3T(n/5)+nlogn
(b) (5%) T(n)=2T(n/2)+$n(logn)^3$
(c) (5%) T(n)=7T(n/3)+n

Ans: (a) T(n)=θ(nlogn) (b) T(n)=$\theta (n(logn)^4)$ (c) T(n)=$\theta (n^{log_3 7})$

4. (10%)

(a) (3%) What is the worst-case running time for the bucket-sort algorithm?
(b) (7%) What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(nlgn)?

Ans: (a)$n^2$, when all items in only one bucket. (b) use quick-sort to sort the elements in the bucket.

5. (10%)

The definition of the longest increasing subsequence(LIS) problem can be described as follows: Given a sequence $(a_1, a_2, ..., a_n)$, find a longest subsequence $(b_1, b_2, ..., b_m)$ such that for every i<j, $b_i
(a) (2%) Give an LIS of sequence <45, 9, 99, 108, 76, 12, 16, 18>.
(b) (8%) Design a dynamic programming algorithm to construct an LIS.

Ans: (a) 9, 12, 16, 18 (b) Sorting, then use LCS algorithm to compute the sorted sequence and unsorted sequence’s LCS, the LCS will be LIS. (LCS Algorithm：Cormen 15.4)

6. (10%)

A shortest path from u to v is a path of minimum weight from u to v. The shortest path weight from u to v is defined as δ(u,v)=min{w(p): p is the path from u to v}, where w(p) is the summation of weights of edges in p. Prove the following two statements briefly.
(a) (5%) A subpath of a shortest path is a shortest path.
(b) (5%) For all u, v, x∈V, we have δ(u,v)≤δ(u,x)+δ(x,v)

Ans: (a) If subpath isn’t shortest path, we can replace the subpath to the shortest subpath, then this path is shorter than the original shortest path, it is impossible. (b) Cormen lemma 24.10

7. (6%)

The Extract-Min and Decrease-Key are two critical modules in the Dijkstra's shortest-path algorithm. Fill in the appropriate complexities in the following table
 Q $T_{Extract-Min}$ $T_{Decrease-Key}$ Total Array O(V) O(1) Binary Heap Fibonacci Heap O(1) amortized

Ans:

 Q $T_{Extract-Min}$ $T_{Decrease-Key}$ Total Array O(V) O(1) O($V^2$ Binary Heap O(log V) O(log V) O((E+V)log V) Fibonacci Heap O(log V) O(1) amortized O(E+VlogV)

8. (5%)

The counting sort takes Θ(n) time for n inputs, however, sorting takes Ω(nlgn) time. Where's the fallacy (misconception)?

Ans: Counting sort isn’t comparison based sorting algorithm.

9. (5%)

Give a problem satisfies: An optimal solution to the problem contains optimal solutions to its subproblems. Explain your reasoning briefly.

Ans: Shortest path problem, subpath must be optimal.

10. (9%)

Given n line segements, does any pair intersect? Give an O(nlgn) algorithm to solve this problem.

Ans: Cormen:33.2