# 2006 F

*219,432*pages on

this wiki

1. (10%) Which ones of the following statements are correct? Please justify your answers:

- a.
- b. lg(n!) = Θ(nlgn)
- c.
- d. a, b are real constants
- e.

Ans:

- a. false, it is .
- b. true, by stirling approximation.
- c. true, it is .
- d. true.
- e. false, it is .

2. (4%) Can the master theorem be applied to the following recurrence? Please justify your answer:

- T(n)=2T(n/2)+nlgn

Ans: Yes, by extended master theorem. T(n)=.

3. (4%) What is the lower bound of any comparison sort algorithm? Can this apply to bucket sort? Justify your answer briefly.

Ans: Lower bound is Ω(nlgn). Bucket sort can not apply this, because it is not comparison based sorting algorithm.

4. (5%) What is the best-case running time of Quicksort? Justify your answer briefly.

Ans: Best-case running time of quicksort is O(nlgn). If we partition two part into equal size, the running time is O(nlgn).

5. (12%) For n distinct elements with positive weights such that , the weighted median is the element satisfying and .

- a. (5%) Show how to compute the weighted median of n elements in O(nlgn) worst-case time using sorting.
- b. (7%) Show how to compute the weighted median of n elements in Θ(n) worst-case time using a linear-time median algorithm.

6. (16%) The matrix-chain multiplication problem can be stated as follows: Given a chain of n matrices, where for i = 1, 2, ..., n, matrix has dimension by , fully parenthesize the product in a way that minimizes the number of scalar multiplications.

- a. (8%) Given the input sequence of dimensions we define m(i,j), i<j, as the minimum number of scalar multiplications needed to compute the matrix . Please give a dynamic programming formula to compute m(i,j).(Remember to specify the initial conditions explicitly.)
- b. (4%) Find an optimal parenthesize of a matrix-chain product whose sequence of dimension is [5, 10, 3, 12, 5, 50, 6]. What is the minimum number o multiplications required?
- c. (4%) What is the time complexity of the formula in (a)?

7. (11%)

- a. (4%) Describe the Dijkstra's algorithm for the single-source all-destination shortest path problem.
- (Please clearly define your notation.)
- b. (4%) Use this algorithm on the following graph to find the shortest paths from the source node a to all the other nodes. (Please show the partial result at each iteration.)
- c. (3%) Give an example to show why the algorithm may not work for a graph with negative weights.

8. (8%)

- a. (2%) Give the definition of topological sort.
- b. (6%) Describe an algorithm based on the depth-first search for solving the topological sort problem.

9. (10%) The knapsack problem is defined as follows: Given positive integers and M. Find such that is minimized subject to . Given a greedy method to find an optimal solution of the knapsack problem and prove its correctness.

10. (10%) The following lists an approximation algorithm for solving the Euclidean traveling-salesperson (ETSP) problem:

- Input: A set of n points in the plane.
- Output: An approximated traveling salesperson tour of S.
- Step 1. Find a minimal spanning tree T of S.
- Step 2. Find a minimal Eucliedan weighted matching M on the set of vertices of odd degree in T. Let G = M∪T.
- Step 3. Find an Eulerian walk of G and use it as the approximated tour of ETSP.

- Show that the length of this approximated TSP tour of S is less than or equal to 1.5 times the length of the optimal TSP tour of S.

11. (10%) The Fibonacci numbers are defined by the recurrence F(n)=F(n-1)+F(n-2), with initial conditions F(0)=0 and F(1)=1. Computing the nth Fibonacci number is easily done in n-1 steps. The divide-and-conquer technique can compute this number with Θ(lgn) operations. Design such an algorithm and justify your answer.

- Hint: Consider the matrix and its powers.

Ans: Q-Matrix method.