CS421 - Advanced Data Structures and Algorithm Development - Week 9 & 10 Assignment

(Homework must be submitted electronically to summers_wayne@ColumbusState.edu or hand delivered to my mailbox by noon MST. )
Late assignments will be subject to up to a 25% deduction in points per day. No credit will be given for assignments that are more than one week late.

DUE March 26, 1999 (13 pts)
1. Finding the Second Best Algorithms
   1. Trace algorithm 3.2, showing your work for the following data: (6 5 1 7 2 9 4 3)
   2. Trace algorithm 3.3, showing your work for the following data: (6 5 1 7 2 9 4 3)
   3. Draw the corresponding binomial tree for the results in (b).
   4. Trace algorithm 3.4, showing your work for the following data: (6 5 1 7 2 9 4 3)
   5. Exercise 14 (pg. 221)
2. DUE March 29, 1999 (13 pts)
   1. Exercise 17 (pg. 221)
   2. Exercise 30a (pg. 223)
   3. Find f(8) where f(n) = 0 if n=1; 1 if n=2; f(floor[n/2]) + f(ceil[n/2])+2 if n > 2 [Show your work!

3. DUE March 31, 1999 (13 pts)
   1. Trace algorithm 3.8 to find the media (i=5), showing your work for the following data: (2 1 7 5 4 3 8 9 6)
   2. Find f(4,1), f(4,2), f(4,3), f(4,4) for formula f(n,i) on the bottom of page 194.
   3. Exercise 30a (pg. 223)

4. Participate in the Collabra discussion group (CS421 on the server cs.nmhu.edu). Discuss searching techniques.