HW1 Clarifications

Some last minute clarifications (compiled from popular questions we received recently). Check back regularly---we will continue to update this entry as we get more questions.

1. Problem 2. A couple of people pointed out that $G_i$, as stated in the hint for question 2b, can be empty, leading to horrible consequences. We were indeed sloppy about the definition of $G_i$. To be more precise, $G_i$ includes all elements of $D_i$ that were ``good'' at some point during $I_i$.
   
   As such, $G_i$ can never be empty, because at most $\alpha n$ elements were corrupted at the beginning of $I_i$ and $D_i$ contains $2\alpha n$ elements.
   
2. Just to be more clear about what assumptions we make about an $\alpha$-relaxed priority queue:
   
   
   
   • At any point in time only $\alpha n$ elements can be ``bad,'' where $n$ here is the number of elements in the priority queue at that moment.
     
   • When an element becomes ``bad,'' it records a time stamp of when it gets "corrupted."
     
   • Once an element becomes ``bad,'' it can never go back to normal. The priority queue may raise the value of an element more than once.
     
   • If an element is bad, its effective priority value is at least the value of its original priority. Note that priority value implies that an element with priority value $9$ is smaller than an element with value $10$, so if your queue has only $9$ and $10$, findMin will report a $9$.
     
   
   
3. Problem 4. The (evil) hint may have led to believe that you can construct $H$ in $O(n^{40})$ time. You should ignore it. Indeed, $H$ will have $O(n^{40})$ nodes, but it will take time $O(n^{80})$ to construct.