# 2005 S

*222,100*pages on

this wiki

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 leaves, each leaves has path length n – 1, so the external path length is .

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)+ 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(), where is the smallest power of 2 greater than or equal to m. Show your reasoning.

Ans: Master Theorem,

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

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(), where k<2. Hint: Represent the matrix as , column vector as 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={} with non-negative integer weights. The weight of is denoted as w().

Partition: Is there a subset A'⊆A for which ? 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 ?

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.