Homework assignments

Homework assignments will usually be given on Thursday afternoon, and are due the following Thursday in class. Deadlines are strict. Please email when there are unforeseen events.
Homework assignment 1 (due Thr, Jan 21st). Read chapters 1 and 2. Do exercises 1.1-4, 1.1-5, 1.2-2, 1.2-3, 2.1-1, 2.1-2 and 2.1-3.
Homework assignment 2 (due Thr, Jan. 28th). Do exercises 2.2-1, 2.2-2, 2.2-4, 2.3.1. Also, prove (using the big Oh definition) that if f(n)=O(g(n)) and g(n)=O(h(n)) then f(n)=O(h(n)).
Homework assignment 3 (due Thr, Feb. 4th). Do exercises 2.3-5, 3.1-3, 3.1-4, 4.5-1, 4.5-2. 
Homework assignment 4 (due Thr, Feb. 18th). Do exercises 2.3-7, 4.4-6, 5.2-1, 5.2-3, 5.2-5, 4.3-1 [Hint: use the substitution method, guessing that T(n) <= cn^2 (reads n squared) for constant c]
Homework assignment 5 (due Thr, Feb. 25th). Do exercise 7.3-1, 9.2-4, 11.2-2, 11.4-1 (only the double hashing)
- Consider an open-address hash table with uniform hashing. What is the expected number of probes (at most) in an unsuccessful search when the load factor is 7/8, and when it is 2/3? 
- Is the average search time in a hash table with collisions resolved by chaining always O(1)? Explain why or why not.
Homework assignment 6 (due Thr, Mar. 3rd). Consider a hash table with collisions resolved by chaining. Assume uniform hashing and that the number of elements n stored in the hash table is 10 times the number of slots. What is the average time for a successful search? 
- Draw all valid Binary Search Trees for the four nodes 1, 2, 3, 5;
Homework assignment 7 (due Thr, Mar. 24th). (a) Draw all valid Binary Search Trees for the four nodes 1, 2, 3, 5; (b) Draw all valid Binary Red Black Trees for the four nodes 1, 2, 3, 5. Note the corresponding Black Height of each node to help convince yourself it is a valid Red Black tree; (c) Exercises 13.1-5, 13.2-1.
Homework assignment 8 (due Thr, Mar. 31st). Do excercises 13.3-1; 13.3-2; 13.3-3, 15.1-3, 15-1-5
Homework assignment 9 (due Thr, Apr. 7th). Do excercises 15.1-2, 15.1-3, 15.4-1. We developed a bottom up solution to the Longest Common Subsequence (see LCS-LENGTH on page 394 in the text book). Describe or write pseudo-code for a Memoized version.
Homework assignment 10 (due Thr, Apr. 14th). 1.) Explain why dynamic programming fails to speed up a good divide-and-conquer algorithm such as merge sort. Illustrate this by considering the sub-problems for an array of size 16.
2. 16.1-2; 16.1-3, 16.3-3 (Explain all steps of generating the Huffman code tree for the given set. There are two ways to combine nodes of equal frequency, such as when you combine 2 and 2. Combine them in a way that gives an obvious pattern to the Fibonacci sequence.)
Homework assignment 11 (due Thr, Apr. 21st). 1.) Do excercises 22.2-4, 22.3-2 (just show start and finish; not edge classification), 22.5-1
2.) Is the topological sort in the Cormen textbook fig 22.7 unique? Are there other ways of sorting? Explain why or why not considering the DFS approach.