# 2005 S

*215,815*pages 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. (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.