# 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.