15-451, Fall 2000 Final Exam SOLUTIONS

1.

a. Theta(n)
b. Theta(n log n)

c. The problem does not state whether the graph is directed or undirected.
   We assume directed, which is the more difficult case.

   Claim: If there is any odd cycle, then there must be some vertex
   for which the shortest cycle through this vertex is of odd length.
   Could use DFS for each vertex to find this: O(mn).

   There might be some way to do this O(m+n), though.

d. F could be a very big number, e.g., 2^100, but since it is encoded in
   binary, the size of the problem would still be small (continuing with
   the example, we only need 101 bits).
e. Solve perfect matching with all capacities = 1.  Algorithm is O(m). The
   max-flow is m, and each step increases the flow by 1 and takes constant
   time (since the path from source to sink is of length 3).

2.

a. True, since a satisfying solution must also be a feasible
   fractional solution.

b. Clauses (a,b), (~a,b), (~a,~b), (a,~b) are not satisfiable, but
   have fractional solution with a = b = 0.5

3.

a. 4
b. 540
c. 1, 4, 11, 14
d. 60
e. 4
f. NOT SAME, since squaring is 2-to-1
g. SAME (since Z*n is group for multiplication)
h  NOT SAME (since Z*n is not group for addition)

4. a. dist(ABCD, EBCD) = 2 != 1+dist(BCD,BCD)
   b. Can build up table dist(X,Y) for every suffix X of S and every suffix
      Y of T, based on this identity.

5. Not covered in Spring, 2001.

6. Can solve using flow network.  Add source, with capacity 1 edge to
   every node s_i, and sink, with capacity 1 edge from every node
   t_i. Also replace every undirected edge (u,v) in G by the following
   network. This ensures that (u,v) is used atmost once.

	    x
	   /|\
	  / | \     The edge directions are u -> x, v -> x,
	 /  |  \    x -> y, y -> u and y -> v. All edges have
	u   |   v   unit capacities.
	 \  |  /
	  \ | /
	   \|/
	    y


7.
 a. insert
 b. successor, findrank
 c. findrank
 d. ismember, successor, findrank
 
 Augment search tree by adding size field to each node.  This records the
 total number of keys in the subtree having this node as root.

 When insert, simply update appropriate counts.  Only changes will be
 children of nodes along insertion path.

8 a. Worst case amortized cost of push is 4.  To see this by induction, suppose
 have grown stack to size 2/3n at cost of 4*2/3n = 8/3n.  Then can do
 1/3n-1 pushes at unit cost, followed by push of cost n+1 to grow stack
 to n+1. Total cost will be (8/3+1/3+1)n = 4n.

  b. No.  Assume have filled array of size n.  Adding one element causes
  increase to size 3/2n.  Popping this element would cause us to shrink array
  to size n.  Keep repeating this to get sequence with amortized complexity
  Theta(n).

  c. Yes.  Get at least 1/6n unit cost operations between any operation
  requiring Theta(n) work.