15-451 Algorithms		09/30/09
							RECITATION NOTES
* Go over quiz questions and hand back quizzes
* Hashing
=======================================================================

Quiz 1
======
- quiz stats: median: 71 middle half 60--79
- this was a difficult quiz with several hard questions.  Probably
  toughest quiz 1 that I (AB) have given in 451.  Don't be
  discouraged - everything is curved in the end.  
- go over the questions.

Specific hard ones:

2(b): instead of doubling the size of the array we first add 1, then add
      2, then add 3, then add 4, etc.

      One way to argue:
      Total number of resizes is O(sqrt(n)), so total time spent doing
      resizing is upper bounded by O(n*sqrt(n)), giving O(sqrt(n)) upper
      bound on amortized cost.  But also have done Omega(sqrt(n))
      resizes ever since the array had n/2 elements, so total time is
      lower-bounded by Omega(n*sqrt(n)), giving Omega(sqrt(n)) lower
      bound on amortized cost.

      Another way to argue: total resizing cost = 
      1 + (1 + 2) + (1 + 2 + 3) + ...+ (1 + 2 + 3 + ... + sqrt(n))

2(c)(i): the first i people are in a random order, so there is a 1/i
	 probability that the tallest of them is at position i.

3(c): need increasing at fast-enough rate that average splits largest
      off from the rest.  One way is n^0, n^1, n^2, n^3, ....


Hashing
=======
- Recap universal hashing.

- Do argument in 10.6.1 of the lecture notes for alternative universal
  hashing scheme using prime-number-sized tables.