But add the space optimization that bucket stores just single entry

Describe how to use a map to implement the dictionary ADT, assuming that the user may attempt to insert entries with the same key.

C-9.2

Design a variation of binary search for performing operation findAll(k) in a dictionary implemented with an ordered search table, and show that it runs in time O(logn + s), where n is the number of elements in the dictionary and s is the size of the iterator returned.

C-9.5

primes up to .)

C-9.7

C-9.9

The quadratic probing strategy has a clustering problem related to the way it looks for open slots. Namely, when a collision occurs at bucket h(k), it checks buckets A[(h(k) + j2) mod N], for j = 1,2,…, N − 1.

C-9.10

Show that the methods above(p) and prev(p) are not actually needed to efficiently implement a dictionary using a skip list. That is, we can implement entry insertion and removal in a skip list using a strictly top-down, scan-forward approach, without ever using the above or prev methods. (Hint: In the
insertion algorithm, first repeatedly flip the coin to determine the level where you should start inserting the new entry.)

C-9.13

Suppose that each row of an n × n array A consists of 1's and 0's such that, in any row of A, all the 1's come before any 0's in that row. Assuming A is already