## FANDOM

232,423 Pages

1. (15%) Consider the graph in Figure 1. Find a minimum-cost spanning tree by Prim's algorithm and by Kruskal's algorithm.

Ans: Trivial.

2. (10%) In Figure 2 use Dikstra's algorithm to find the shortest paths from node a to other vertices.

Ans: Trivial.

3. (5%) The external path length of a rooted tree is the sum over all leaves of the lengths of the from the root to each leaf. What is the external path length of a full binary tree with n levels?

Ans: Level n has $2^n$ leaves, each leaves has path length n – 1, so the external path length is $(n-1)2^n$.

4. (10%) Given tight big-oh and big-omega upper and lower bounds on the function T(n) defined by:

T(1)=1
T(n)=4T(n/2)+$n^2$ for n=2, 4, 8...

Your bounds need apply only when n is power of 2, i.e., you may assume that for all m, T(m)=T($2^k$), where $2^k$ is the smallest power of 2 greater than or equal to m. Show your reasoning.

Ans: Master Theorem, $\theta (n^2logn)$

5. (10%) Let $S_1,S_2, ..., S_k$ be sets of integers in the range 1 to n, where the sum of the cardinalities of the $S_i's$ is n. Describe an O(n) time algorithm to sort all of the $S_i's$.

Ans: Counting sort

6. An n by n Toeplitz matrix A is a matrix with the property that

A[i,j]=A[i-1,j-1], 2≤i,j≤n.
(a) (10%) Find a representation for a Toeplitz matrix so that two n by n Toeplitz matrices can be added in O(n) operations.
(b) (15%) Find a divide-and-conquer algorithm for multiplying an n by n Toeplitz matrix by a column n-vector. What is the time complexity of your algorithm? Note: to get credit for this question your algoritm must run in time O($n^k$), where k<2. Hint: Represent the matrix as $\begin{bmatrix} a & b \\ c & a \end{bmatrix}$, column vector as $\begin{bmatrix} x \\ y \end{bmatrix}$ and let
T1=a*(x+y)
T2=(b-1)*y
T3=(c-a)*x

Ans: (a) Toeplitz matrix is defined by first column and row, we can add two Toeplitz matrix’s first column and row in O(n) time. (b) no answer

7. (15%) Given that the Partition Problem (PP, defined below) is NP-complete, you are to sketch a proof that the Restricted Partition Problem (RPP, defined below) is also NP-Complete.

Given: Finite set A={$a_1, a_2, ..., a_k$} with non-negative integer weights. The weight of $a_i$ is denoted as w($a_i$).

Partition: Is there a subset A'⊆A for which $\sum_{a_i \in A'}w(a_i)=\sum_{a_j \in A-A'}w(a_j)$? i.e., Can A be partitioned into two disjount sets whose weights are the same?

Restricted Partition: Is there a subset A'⊆A containing k/2 members (i.e., half the elements of A) such that $\sum_{a_i \in A'}w(a_i)=\sum_{a_j \in A-A'}w(a_j)$?