HW 2
			due:  Thursday, Feb. 12
		(Extension:  due Thursday, Feb. 19)

NOTE:  There will shortly be a new course on-line web page on recurrence
 relations, O() formulas, models of computation and all that.  Please
 look for it.

The homework consists of recurrence relations and exercises on depth
first search.  We did not discuss directed graph or strongly connected
components in Chapter 3.  The concept is simple.  Please study it from the
textbook:  section 3.3 and 3.4 of the textbook.

1.  Recurrence Relations 
   Please use the guess and check method.  In particular, first show
    the values of the constant coefficient that you compute, and
    then show the O() formula.

 a.  A problem takes an input of size n, splits it into 7 subproblems
    of size n/2 and requires time n^2 to combine the subproblems.

 b.  A problem takes an input of size n, requires time n to reduce it
    to a single subproblem of size n-1, and then uses the subproblem
    answer to produce the answer in time log n.

 c.  A problem takes an input of size n, reduces it to a subproblem
    of size square root of n, and requires unit time (time 1) to produce
    the answer from the result of the subproblem.

 d.  The mergesort algorithm takes an input of size n, splits it into
    two subproblems of size n/2, and then requires time n to combine the
    subproblems.  What is the time to compute a problem of size n.
    (Recall from class that in this case, you may be able to simplify
    the recurrence relation by subtracting the same dominant term from the
    left hand side and the right hand side.  You can then take a ratio
    of the remaining left hand side and right hand side.

  e.  A problem takes an input of size n, splits it into 3 subproblems of
    size n/2, and then combines them in time n log n.  What is the time?

  f.  A problem takes an input of size n, requires 1/n time to reduce the
      problem to a subproblem of size n-1, and then requires constant time
	(assume unit time) to produce the answer from the subproblem.

  g.  A problem takes an input of size n, requires time n to reduce the
      problem to the square root of n subproblems, where each subproblem
      is of size square root of n, and then requires log n time to combine
      the subproblems.

2.  Exercise 3.4
3.  Exercise 3.10
4.  Exercise 3.16
5.  Exercise 3.25
6.  Exercise 3.28