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.