Assigned:
Wed 12 Sep 2012
Due:
Wed 19 Sep 2012
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 "-2" in the T(n/3 - 2) 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. 58 for the definition of lg*.
Hint: This problem has a five line solution. You'll need to think "out of the box."