Fandom

Scratchpad

2005 S

215,815pages on
this wiki
Add New Page
Discuss this page0 Share

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

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.

Also on Fandom

Random wikia