Project 2 CS 313 Spring 2021
A dictionary is a data structure for storing a set S of items that supports three
basic operations: Search(x) which returns True if x ∈ S or False, otherwise;
Insert(x) which adds the item x to the current set S; and Delete(x) which re-
moves x from S. There are several implementations for this data structure each
with varying levels of efficiency. For example, a linked list can support all three
operations in time O(n), O(1), and O(n), respectively and where |S| = n. Both
the runtime of Insert and Delete can be improved by using a binary-search tree,
which give a worst-case O(log n). A more scalable implementation of a dic-
tionary is based on hashing, which provides insertion in O(1) time and O(1)
time insertion and deletion in expectation. This result is dependent on the
manner in which hash function distributes the elements and the collision reso-
lution scheme employed. This project it to learn a fascinating open addressing
technique, cuckoo hashing.
2 Cuckoo Hashing
Cuckoo hashing exploits the idea of maintaining a two level hash table to resolve
collisions. If while inserting an element occupies a given position, rehash the
occupant using another, independent hash function. The benefits of such a
construction is that querying now takes O(1) time in the worst-case and not just
in expectation. The construction and the query algorithms are listed below.
2.1 Motivation and Design
Maintain two hash tables T1 and T2, via two independent hash functions h1 and
h2, respectively. Instead of requiring that an element x be associated with a
single position in the table indexed by h(x), we provide two alternative positions
within table T1 and T2, T [h1(x)] and T [h2(x)], respectively. When inserting a
new element y it may happen that there is no space available, since both the
position h1(y) and position h2(y) are occupied by other objects, say a and b. To
deal with such an even, we throw out the current occupant a in the first table,
and rehash a into the second table. A collision can occur when hashing element
a into table T2, so this process is repeated; see figure 1.
Figure 1: Construction Algorithm for Cuckoo Hashing
We now present the following insertion and query algorithms.
Given a set S ⊂ U of n elements from a large universe U . We can construct the
data structure as follows.
2.2.1 Construction Algorithm:
• Choose two independent hash functions: h1 : U → [m] and h2 : U → [m].
• Insert each element using h1.
• If while inserting, we detect a collision, say h1(xi) = h2(xj) where i 6= j
and xi is the element currently being inserted, rehash xj using h2.
• If we detect a collision say with element xk on the second level, rehash the
xk using h1.
Given a query q ∈ U , we have the following search algorithm.
2.2.2 Query Algorithm:
• compute h1(q).
• If you’ve found q, return 1
• Otherwise, compute h2(q), and return 1 if found.
• If q is not in h2(q), return 0.
3.1 Algorithmic Problem
Consider the following strategy for multiplying two sparse univariate polynomi-
als P1 and P2 of size K and L, respectively. Each polynomial is represented as
a linked list of nodes consisting of a coefficient and an exponent. We multiply
each term in P1 by a term in P2 for a total of KL multiplications. One method
is to sort these terms and combine like terms, but this requires sorting KL
records which could be expensive. Alternatively, we could merge terms as they
are computed and them sort the result.
1. Write a program to implement the alternative strategy.
2. Determine the running time of both methods if the polynomials have
O(K + L) terms.
Implement the above data structure using Java 8 and use it to implement the
alternate strategy for multiplying two polynomials. Your program should take a
text file from the command line and compile under the standard javac compiler
in Linux. Each line of the text file will consist of a single polynomial. Every two
consecutive polynomials are the terms to be multiplied. Let p1 and p2 be the
input polynomials and let p3 the polynomial of the result, your program should
print the answer in the following format:
(p1)(p2) = p3.
For example, if line i has the the polynomial 3x2 and line i + 1 has the
polynomial 4x2 − 5x + 7, then you should print to the console:
(3x2)(4x2 − 5x + 7) = 124 − 10x3 + 21x2.
3.3 Java Libraries
You may utilize the following standard hashing library:
All files will be submitted in a zip file to blackboard.
4 Due Date
Please submit by 11:59 PM on 5/4/2021.
Motivation and Design