# CMPT 231 Fall 2013 HW Assignments

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.

## HW1 (due Thu 26 Sep) (40pts)(solns)

• p.22: 2.1-1, 2.1-3
• p.29: 2.2-3
• p.37: 2.3-1, 2.3-4, Problem 2-2
• p.53: 3.1-7
• 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.)

## HW2 (due Thu 10 Oct) (40pts)(solns)

• (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?

## HW3 (due Thu 24 Oct) (40pts)(solns)

• p.185: 7.4-5
• p.186: 7-2
• p.188: 7-4
• 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.)

## HW4 (due Thu 7 Nov) (40pts)(solns)

• p.241: 10.2-7
• p.248: 10.4-3
• p.293: 12.2-4
• p.299: 12.3-4
• p.303: 12-2
• p.370: 15.1-2
• p.378: 15.2-1
• p.389: 15.3-2
• p.389: 15.3-5
• p.404: 15.5-2

## HW5 (due Fri 22 Nov) (40pts)(solns)

• 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.
• p.427: 16.2-1
• p.436: 16.3-3 , 16.3-8

## HW6 (due Thu 5 Dec) (40pts)(solns)

• p.593: 22.1-5
• p.602: 22.2-8 (hint: it's a tree, not a general graph)
• p.610: 22.3-2
• p.620: 22.5-2
• p.637: 23.2-2, 23.2-4
• p.654: 24.1-1