> 1. In the discussion of quadratic probing in the lecture, > why is it that the initial hash index is always zero. > It would seem that the problem of having a "virtually > full" table wouldn't apply if the quadratic probing > were used as the double hash condition.
I think you are right on the money. We are just using 0 as the "typical" value. Say you hash to 13, and that is full: you next probe 14 (13 + 1), 17 (13 + 4), and so on. > 2. In the part of lecture dealing with the > "Expected number of comparisons" and the > discussion that chances are 1/2 for one try, > 1/4 for the second, etc. Since the table is > half full, isn't this analogous to flipping > a coin where no matter how many times you > have previously flipped it, the chances are > always 1/2 that you will get the side you > want. In our case an open spot? RIght. The odds are simply culminative. Assume that you sell icecream cones at variable cost. The buyer flips a coin, and pays $1 each time he flips. He has to flip until he gets a heads. The chances of taking exactly two flips are 1/4 because if he got a heads on the first flip (1/2 of the time) he stops there. He pays exactly $2 1/4 of the time: the odds of flipping TH. He pays $3 if he flips TTH (odds 1/8) and so on. - jeff parker
