2005 S

222,100pages on
this wiki
Add New Page
Discuss this page0 Share

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(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

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)?

Ans: No answer.

8. (10%) We have a directed graph G=(V,E) represented using adjacency lists. The edge costs are integers in the range {0, 1, 2, ..., 10}. Assume that G has no self-loops or multiple edges. Show that the single-source shortest path problem on G can be solved in linear time i.e., O(|V|+|E|).

Ans: BFS, for any edge, we create weight – 1 dummy node, just like transform weighted graph to unweighted graph, then you BFS, we can find the shortest path.

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.