please comment out each line of code to have a better understainding.
Project 2 CS 313 Spring 2021 Paul Cesaretti 1 Objective 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. 1 Figure 1: Construction Algorithm for Cuckoo Hashing We now present the following insertion and query algorithms. 2.2 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. • Repeat. Given a query q ∈ U , we have the following search algorithm. 2 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 Problem 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. 3.2 Implementation 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: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html 3 3.4 Submission All files will be submitted in a zip file to blackboard. 4 Due Date Please submit by 11:59 PM on 5/4/2021. 4 Objective Cuckoo Hashing Motivation and Design Algorithms Construction Algorithm: Query Algorithm: Problem Algorithmic Problem Implementation Java Libraries Submission Due Date Project 2 CS 313 Spring 2021 Paul Cesaretti 1 Objective 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. 1 Figure 1: Construction Algorithm for Cuckoo Hashing We now present the following insertion and query algorithms. 2.2 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. • Repeat. Given a query q ∈ U , we have the following search algorithm. 2 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 Problem 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. 3.2 Implementation 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: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html 3 3.4 Submission All files will be submitted in a zip file to blackboard. 4 Due Date Please submit by 11:59 PM on 5/4/2021. 4 Objective Cuckoo Hashing Motivation and Design Algorithms Construction Algorithm: Query Algorithm: Problem Algorithmic Problem Implementation Java Libraries Submission Due Date