Suppose you are given a sorted array, A,ofn distinct integers in the range from
1 to n+1,sothereisexactlyoneintegerinthisrangemissingfromA. Describe
an O(logn)-time algorithm for finding the integer in this range that is not in A.
C-3.2 Let S and T be two ordered arrays, each with n items. Describe an O(logn)-
time algorithm for finding the kth smallest key in the union of the keys from S
and T (assuming no duplicates).
C-3.3 Describe how to perform. the operation findAllElements(k),whichreturnsevery
element with a key equal to k (allowing for duplicates) in an ordered set of n key-
value pairs stored in an ordered array, and show that it runs in time O(logn+s),
where s is the number of elements returned.
C-3.4 Describe how to perform. the operation findAllElements(k),asdefinedinthe
previous exercise, in an ordered set of key-value pairs implemented with a binary
search tree T,andshowthatitrunsintimeO(h + s),whereh is the height of T
and s is the number of items returned.
C-3.5 Prove, by induction, that the height of a binary search tree containing n items is
at least ⌈log(n +1)⌉.
C-3.6 Describe how to perform. an operation removeAllElements(k),whichremoves
all key-value pairs in a binary search tree T that have a key equal to k,andshow
that this method runs in time O(h + s),whereh is the height of T and s is the
number of items returned.
C-3.9 Suppose n key-value pairs all have the same key, k,andtheyareinsertedintoan
initially empty binary search tree using the algorithm described in Section 3.1.3.
Show that the height of the resulting tree is Θ(n).Also,describeamodifica-
tion to that algorithm based on the use of random choices and show that your
modification results in the binary search tree having height O(logn) with high
probability.
Hint: You may need to add a new eld to each node; see slides.
6. (10pt) Problem A-1.11 from textbook
1.5. Exercises 49
very deadly; just one drop diluted even a billion to one will still kill someone.
Even so, the poison works slowly; it takes a full month for the person to die.
Design a scheme that allows the evil king to determine exactly which one of
his wine bottles was poisoned in just one month’s time while expending at most
O(logn) of his taste testers.
Note: All the remaining problems are inspired by questions reported to have been
asked in job interviews for major software and Internet companies.
A-1.5 Suppose you are given a set of small boxes, numbered 1 to n,identicalinevery
respect except that each of the first i contain a pearl whereas the remaining n−i
are empty. You also have two magic wands that can each test whether a box
is empty or not in a single touch, except that a wand disappears if you test it
on an empty box. Show that, without knowing the value of i,youca usethe
two wands to determine all the boxes containing pearls using at most o(n) wand
touches. Express, as a function of n,theasymptotic umberofwandtouches
needed.
A-1.6 Repeat the previous problem assuming that you now have k magic wands, with
k>2 and kof wand touches needed to identify all the magic boxes containing pearls.
A-1.7 Suppose you are given an integer c and an array, A,indexedfrom1 to n,ofn
integersintherangefrom 1 to 5 n(possiblywithduplicates). Describeanefficient
algorithm for determining if there are two integers, A[i] and A[j],inA that sum
to c,thatis,suchthatc = A[i]+A[j],for1 ≤ itime of your algorithm?
A-1.8 Given an array, A,describeanefficientalgoithmforreversingA.Forexample,
if A =[3, 4 , 1, 5],thenitsreversalisA =[5, 1, 4 , 3].YoucanonlyuseO(1)
memory in addition to that used by A itself. What is the running time of your
algorithm?
A-1.9 Given a string, S,ofn digits in the range from 0 to 9,describeanefficient
algorithm for converting S into the integer it represents. What is the running
time of your algorithm?
A-1.10 Given an array, A,ofn integers, find the longest subarray of A all the
numbers in that subarray are in sorted order. What is the running time of your
method?
A-1.11 Given an array, A,ofn positive integers, each of which appears in A exactly
twice, except for one integer, x,describeanO(n)-time method for finding x
using only a single variable besides A.
A-1.12 Given an array, A,ofn−2 unique integers in the range from 1 to n,describean
O(n)-time method for finding the two integers in the range from 1 to n that are
not in A.YoumayuseonlyO(1) space in addition to the space used by A.
A-1.13 Suppose you are writing a simulator for a single-elimination sports tournament
(like in NCAA Division-1 basketball). There are n teams at the beginning of
the tournament and in each round of the tournament teams are paired up and the
games for each pair are simulated. Winners progress to the next round and losers
are sent home. This continues until a grand champion team is the final winner.
Hint: Think of an operation that would remove the paired integers, one by one.
7. (40pt) Write a program, testHashing.py, to implement and compare linear probing and double
hashing. Create two classes, HashTable LinearProbing and HashTable DoubleHashing, that im-
plement hash tables with linear probing and double hashing, respectively. The tables store pairs
(key, value); each such pair can be an object of a storage class, say MapEntry. The table size is
xed at size = 1000003 (that is a prime number). The hash function to be used is:
abs(hash(key)) % size.
The step for linear probing is 1 and for double hashing is:
1 + abs(hash(key)) % (size - 2).
When removing elements from the table, they are replaced by a special value REMOVED which is
di erent from any possible element, including empty cells. When searching, REMOVED is treated like
any other element. When inserting a new key, if a REMOVED position is found during the search,
then it is used for insertion.
Create an array data of size elements and ll it up with random numbers in the interval 1 to one
billion; you can use:
random.randint(1, 1000000000).
A set of load factors is given:
load = [.25, .5, 2/3.0, .75, .8, .9, .95]
You need to test the performance of the hash tables for each load factor given, load[i], as indicated
by the average number of probes in each table. For a given load factor load[i], insert the rst
load[i] * size elements from data.
For successful search, generate an array of 0.01 * size random elements from the rst load[i] *
size elements of data, that is, what is already in the table. Then count the number of probes while
searching for these elements in the hash tables and then divide by their number, 0.01 * size, to
obtain the average.
For unsuccessful search, count the number of probes while inserting the following 0.01 * size
elements from data and report the average.
You do not need to restart inserting from the beginning for each load factor. You can continue
inserting until the next load factor.
Below is what an output of testHashing.py should look like (there will be variations due to
randomness of the process):