CSCI 356 Midterm
Fall 2003

Show all work. Partial credit is granted for sound reasoning.

1. (40 points) Time Analysis: The time complexity of a certain algorithm satisfies the recurrance T(1)   =   8,     T(n)   =   T(n-1) + 4n(n+1)3^n-1
   a. Prove that T(n)   =   (2n² + 1)3ⁿ   -   1.      (Note: this is the "pattern" you do not need to determine the pattern, you need to prove that it is correct.)

   b. Determine whether or not T(n) is O(n³ 3ⁿ) and verify that your answer is correct.

2. (30 points) Greedy: Let G = (V, E) be an undirected graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover is one with the lowest number of vertices. Consider the following greedy algorithm for this problem:

   1. Algorithm Cover(V, E)
   2. {
   3.   	U: = Ø ;
   4.         repeat
   5.         {
   6.               Let q be a vertex from V of maximum degree;
   7.                Add q to U; Eliminate q from V;
   8.                E: = E - { (x,y) such that x = q or y = q};
   9.           } until ( E = Ø );  // U is the node cover
   10.   }
   

   Does this algorithm always generate a minimum node cover? Explain your answer.

3. (30 points) Dynamic Programming:
   a. Let G be a directed graph whose adjacency matrix is A. The transitive closure of a directed graph G = (V, E) whose adjacency matrix is A is defined to be a matrix A* where
   A* = {   1     if there is a directed path from i to j
                  0     otherwise
   for all i, j V.

   Suppose V = {1, 2, . . . , n}. A dynamic programming formulation computes the matrix A^k where

   A^k(i, j) = { 1     if there is a directed path from i to j passing only through nodes in {1,2,...,k}
                       0     otherwise
   for all i, j V.

   We start with A⁰ = A and it is easy to see that A^* = Aⁿ. Describe how you would compute A^k from A^k-1. What is the worse case time complexity for computing A^*?

   b. State the dynamic programming algorithm formulation for finding the shortest path from s to t in a multistage graph where s and t are nodes in the first and last stages respectively.

EXTRA: (10 points) (only try when numbers 1-3 are completed)
Let G = (V, E, w) be a weighted undirected graph with all weights positive and distinct. Let {A, B} be a partition of V, i.e,

A U B = V, A B = Ø , A Ø , B Ø