# 2006 F

215,866pages 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.

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})$

Ans:

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:

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

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 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 $$ 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.
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.