Computer Science 282
Homework
Fall 2004
 Homewrok 9

Due Tuesday Dec 7
 CLRS 19.24 (correctness of heap union)
 CLRS 22.34 (depthfirst search)
 CLRS 221 (breadthfirst search)
 Homework 8

Due Tuesday Nov 16
 CLRS 18.15 (redblack vs. BTrees)
 CLRS 18.26 (complexity in t)
 Homework 7

Due Tuesday Nov 9
 CLRS 162 (scheduling)
 CLRS 172 (binary search)
 Homework 6

Due Tuesday Nov 2
 CLRS 151 (bitonic euclidean traveling salesman)
 CLRS 154 (planning a company party)
 Homework 5

Due Tuesday Oct 26
 CLRS 142.2 (rb tree black height)
 CLRS 142.3 (rb tree depth)
 CLRS 141 (point of maximum overlap)
 CLRS 15.14 (assembly space requirement)
 Homework 4

Due Thursday Oct 7
 CLRS 124 (number of binary trees)
 CLRS 13.36 (rb insert implementation)
 Homework 3

Due Thursday Sept 30
 CLRS 83 (sorting variablelength items)
 CLRS 92 (weighted median)
 CLRS 111 (longest probe bound for hashing)
 Homework 2

Due Thursday Sept 23
 CLRS 6.58 (algorithm for merging lists)
 CLRS 75 (median of 3 partition)
 CLRS 76 (fuzzy sorting of intevals)
 Homework 1

Due Thursday Sept 16
 CLRS 2.37
 CLRS 22
 Solve the following recurrence exactly:
T(1) = 2, and for all n ≥ 2 a power of three, T(n) = 4T(n/3) + 3n +5.
gildea @ cs rochester edu
November 30, 2004