Homework 1
		  due Monday, Jan. 26

1. Hashing:
    Read the Wikipedia article on Bloom filters:
	  http://en.wikipedia.org/wiki/Bloom_filter
	and then consider what happens if you fix the length
	of the bit array at m bits, but you allow the number of
	hash functions, k, to vary.
	a.  What goes wrong in the extreme limit when k becomes large?
	b.  What goes wrong in the extreme limit when k becomes 1?

2. Exercise 2.4:
    Comment:  The book expects you to use a recurrence formula.
	But there is a simpler way:  guess and check.
	Guess that T(n) = O(n^k)  (and lower bound:  T(n) = Omega(n^k) ).

	So, given an estimate of the time of an algorithm in the
	form of a recurrence relation,
	replace T(n) by n^k, and check when the limit for large n of the
	left hand side over the right hand side equals 1.

	Example:  Recurrence relation:  T(n) = 3 T(n/2) + n
	Replace T(n) by n^k for an unknown exponent k:
	  n^k = 3 (n/2)^k + n
	Take the limit:
	  lim_{n->infinity} [n^k] / [ 3 (n/2)^k + n] = 1.
	Solve:
	   lim_{n->infinity} [n^k] / [ 3 (n/2)^k + n = 1/(3 / 2^k) = 2^k / 3
	So:
	  2^k / 3 = 1
	So:
	   2^k = 3
	So:
	   k = log_2 3  (log base 2 of 3)

3. Exercise 2.7.

4. Online notes on fast polynomial multiplication:
	Look at the table for P_{0 mod 4}(), P_{1 mod 4}(), ....
	Then find:  P){0 mod 8}(), P_{1 mod 8}(), ..., P_{7 mod 8}()

5. Exercise 2.10.