2006 F

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

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

a. 3n^2 - 100n + 6 = O(n)
b. lg(n!) = Θ(nlgn)
c. n! = O(n^n)
d. (n+a)^b = \Theta(n^b) a, b are real constants
e. (n+a)^b = \Omega(n^{b+1})


a. false, it is \Theta(n^2).
b. true, by stirling approximation.
c. true, it is o(n^n).
d. true.
e. false, it is \Omega(n^b).

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


Ans: Yes, by extended master theorem. T(n)=\Theta(nlg^2n).

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 x_1, x_2, ..., x_n with positive weights w_1, w_2, ..., w_n such that \sum_{i=1}^n w_i=1, the weighted median is the element x_k satisfying \sum_{x_i<x_k}^{} w_i \leq \frac{1}{2} and \sum_{x_i>x_k}^{} w_i \leq \frac{1}{2}.

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 <A_1, A_2, ..., A_n> of n matrices, where for i = 1, 2, ..., n, matrix A_i has dimension p_{i-1} by p_i, fully parenthesize the product A_1A_2...A_n in a way that minimizes the number of scalar multiplications.

a. (8%) Given the input sequence of dimensions [p_0, p_1, ..., p_n] we define m(i,j), i<j, as the minimum number of scalar multiplications needed to compute the matrix A_{i,j}=A_1A_2...A_n. 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 P_1, P_2, ..., P_n, W_1, W_2, ..., W_n and M. Find X_1, X_2, ..., X_n, 0\leq{X_i}\leq{1} such that \sum_{i=1}^n P_iX_i is minimized subject to \sum_{i=1}^n W_iX_i \leq M. 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 \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} and its powers.

Ans: Q-Matrix method.

Also on Fandom

Random wikia