CMPT 231 Fall 2012 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 27 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 11 Oct) (40pts) (solns)

p.74: 4.1-3 (in Python, consider timeit)
p.83: 4.2-6
p.93: 4.4-5
p.108: 4-3(ace)
p.156: 6.2-1, 6.2-5
p.174: 7.1-2
p.178: 7.2-4
p.185: 7.4-5

HW3 (due Thu 25 Oct) (40pts) (solns)

p.199: 8.3-1
p.204: 8.4-2 (hint: break its assumptions), 8.4-4
p.206: 8-4 (hints: (a) algo is very simple/naive; (b) use decision-tree)
p.261: 11.2-2 , 11.2-3
p.269: 11.3-3 (see top of p.263 for radix 2^p)
p.277: 11.4-1

HW4 (due Thu 8 Nov) (40pts) (solns)

(For all programming exercises, demonstrate your code running on sample input. You may want to attach your code separately from the rest of your assignment.)
p.236: 10.1-5
p.241: 10.2-6: also implement Intersection (only elements that are in both sets), as efficiently as you can
p.250: 10-2a (pseudocode is fine)
p.289: 12.1-4
p.293: 12.2-6 (prove!)
p.303: 12-1 , 12-2

HW5 (due Thu 22 Nov) (40pts) (solns)

p.497: 18.2-1 , 18.2-4 , 18.2-7
p.502: 18.3-1
p.370: 15.1-3
p.378: 15.2-1 , 15.2-3 , 15.2-4
p.390: 15.3-6 (assume a currency cannot be repeated within a sequence of trades)

HW6 (due Thu 6 Dec) (40pts)

p.404: 15.5-2
p.406-412: Choose one of: 15-5, 15-6, 15-7, 15-8, 15-10, 15-12. 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.
16.1-1, 16.1-3