Assigned:
Wed 13 Sep 2006
Due:
Wed 20 Sep 2006
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 5 of the following 6 problems
Points: 20 pts per problem
Note: Part (h) is essentially a problem on bounding a summation; consider the technique we discussed in class.
Hint: Do you think that the "+5" in the T(n/3 + 5) makes any difference, asymptotically? What about the "/2" in the additive term "n/2"? Perhaps you can come up with a good guess and then prove that guess correct...
See CLRS pg. 55 for the definition of lg*.
Hint: This problem has a five line solution. You'll need to think "out of the box."