HW3 Solutions Page

After grading, I selected from amongst the better homeworks the solution below. The student or students that had their homework chosen received 1 bonus point after curving for having their homework selected. If you were chosen and would rather your homework not be used as the solution let me know and I will choose someone else's homework and they will receive the bonus point instead. There was no solution that got full credit. In particular, the solution below should have given a better argument for the average case of problem 5.1. First, in the average case, you should argue if each of the terms is equally likely and occurs in a document with some probability `p`, then the total expected number of query terms to see in a particular document will be `Theta(1)`, so the sub-while loop of our query processing algorithm will take on average `Theta(1)` time. Next one can argue in the average case, the odds that the `t > k` seen document in the posting list is in the top `k` will be `k/t`. So the total number of times we'd expect to have to adjust the result heap in the average case is at most `sum_{t = 1}^N_q k/t < k log (N_q +1)`, and only in these would we potentially need to spend the `Theta(log k)` to make the adjustment. Since we can assume `N_q > > k`, we'll have total time `k (log(N_q +1)) log k < Theta(N_q)` spent through the while loop on iterations where we had to adjust the result heap. In all other times through the while loop we'd only need to spend `Theta(1)`. This gives `Theta(N_q) + Theta(N_q) = Theta(N_q)` total time.

[Hw3 Solution-ZIP]