These corrections are with reference to the literature page of the course.

Leftists Heaps [T83]

Page 38, Fig. 3.5: The rank of node 14 should be 1; not 2.

Skip Lists [P89]

Page 440, last line: A check for an empty list (size(list) = 0) should be inserted to avoid the call L(0) which will take the logarithm of zero.

Page 441, Fig. 7: The first reference to q on the right-hand side should be a p, i.e., the 4th line of the figure should read as follows: q ← forward(p)[level].

Cuckoo Hashing [P06]

Page 4, Fig. 2: It's not important for the analysis, but just before the loop, I would insert if T[pos] ≠ NULL then pos ← h₂(x).

Page 5, line 5 of the proof: The equality should be ≤.

Page 6, line 15: One can do as in the paper, but I would prefer not to allow growth beyond n, which has been defined as the largest number of allowed elements in the structure. I would assume that the εn insertions stay under n. If we come up to the maximum and want to insert, we reallocate to a larger table at that point using doubling techniques and global rebuilding.

Page 6, line 20: Rehashing must cost O(r). This is not a problem, though. We just shouldn't make r too large. If r ∈ O(n), everything's fine.