# 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.2Design 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 timeO(logn+s), wherenis the number of elements in the dictionary andsis the size of the iterator returned.

C-9.5primes up to .)

C-9.7

C-9.9The 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 bucketsA[(h(k) +j2) modN], forj= 1,2,…,N− 1.

C-9.10Show 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.13Suppose that each row of an

n×narray A consists of 1's and 0's such that, in any row ofA, all the 1's come before any 0's in that row. AssumingAis already