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.