All homeworks should be turned in electronically to myCourses.
Homeworks are due by 10pm on the due date.
Unless otherwise noted, all assignments are from the textbook,
CLRS3.
p.60: 3.2-8 (prove), Problem 3-3 (Prove or justify each step of your ranking!
You may use the properties mentioned in the chapter, including Stirling's equation.)
(When solving recurrences, recursion diagrams are useful but not sufficient for proof.
Either induction ("substitution") or the master method are sufficient for proof.)
p.74: 4.1-2
p.87: 4.3-6
p.93: 4.4-8 (verify your bound using induction)
p.97: 4.5-5
p.107: 4-1(cdeg)
p.154: 6.1-6
p.160: 6.4-3
Supplemental #1: Illustrate the operation of Heapsort on the array A=[3, 5, 9, 1, 8, 2, 4, 7, 10]. How many swaps are performed?
p.197: 8.2-4 (Preprocessing step is Θ(n+k) and takes the n integers as input. Last step is O(1) and takes a,b as input.)
p.204: 8.4-4
p.261: 11.2-2
p.282: 11-1 ("uniform hashing": see top of p.259)
(For discrete variables X, the expected value is
E[X] = Σk Pr{ X == k }, i.e., the probability
that X takes on a given value, summed over all possible values of X.)
p.406-412: Choose one of the 12 problems (15-1 to 15-12).
(Some of them, e.g., 15-2 and 15-5, may benefit from reading section 15.4.
Others, e.g., 15-1 and 15-7, may benefit from ch22.)
Code your own implementation to solve the problem using bottom-up dynamic programming,
and demonstrate your code running on sample input.
User interface is your choice and can be rudimentary.
You may want to attach your code files separately from the rest of the assignment.
Be sure to answer any questions given in the problem statement.