Computer Science 282
Homework
Fall 2004
- Homewrok 9
-
Due Tuesday Dec 7
- CLRS 19.2-4 (correctness of heap union)
- CLRS 22.3-4 (depth-first search)
- CLRS 22-1 (breadth-first search)
- Homework 8
-
Due Tuesday Nov 16
- CLRS 18.1-5 (red-black vs. BTrees)
- CLRS 18.2-6 (complexity in t)
- Homework 7
-
Due Tuesday Nov 9
- CLRS 16-2 (scheduling)
- CLRS 17-2 (binary search)
- Homework 6
-
Due Tuesday Nov 2
- CLRS 15-1 (bitonic euclidean traveling salesman)
- CLRS 15-4 (planning a company party)
- Homework 5
-
Due Tuesday Oct 26
- CLRS 14-2.2 (rb tree black height)
- CLRS 14-2.3 (rb tree depth)
- CLRS 14-1 (point of maximum overlap)
- CLRS 15.1-4 (assembly space requirement)
- Homework 4
-
Due Thursday Oct 7
- CLRS 12-4 (number of binary trees)
- CLRS 13.3-6 (rb insert implementation)
- Homework 3
-
Due Thursday Sept 30
- CLRS 8-3 (sorting variable-length items)
- CLRS 9-2 (weighted median)
- CLRS 11-1 (longest probe bound for hashing)
- Homework 2
-
Due Thursday Sept 23
- CLRS 6.5-8 (algorithm for merging lists)
- CLRS 7-5 (median of 3 partition)
- CLRS 7-6 (fuzzy sorting of intevals)
- Homework 1
-
Due Thursday Sept 16
- CLRS 2.3-7
- CLRS 2-2
- 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