CSCI 4470/6470                      Algorithms                         Fall 2009


                                 Homework Set #9

               Due at the start of class on Tuesday October 27 
               OR by 5:30 PM that day in 423 Boyd (under door is okay)


All exercises and problems are from the class text except for Q1 below. 
Be sure to justify your answers.

For everyone:

 Q1 (20 points)
 Exc. 24.2-1 (10 points)
 Exc. 24.2-3 (10 points)
 Exc. 24.2-4 (10 points; given (G,s) where G is a DAG and s is a vertex, your
    algorithm should find the number of s-to-u paths in G for each vertex u.)
 Exc. 24.3-1 (10 points)
 Exc. 24.3-4 (10 points)
 Exc. 24.4-1 (10 points)

Graduate or bonus credit:

 Exc. 24.5-8 (20 points; give a careful proof.  The sequence is to be a series
    of edges (with repetitions allowed), each of which is relaxed in its turn
    in the series.)

--------------------------------------------------------------------------------

Q1: for (a) and (b) give careful, complete proofs based on the definitions
    of "asymptotically positive" and "little-oh( )".  The hypotheses for 
    both parts (a) and (b) are:
      f(n) and g(n) are asymptotically positive;
      f(n) = little-oh(g(n));
      h(n) = (f(n)g(n))^{1/2} (the geometric mean of f(n) and g(n).

(a) Prove that f(n) = little-oh(h(n)).

(b) Prove or disprove that h(n) = little-oh(g(n)).