CIS 263

Hash

Fall 2019

Insertion and Rehashing

Step through various hash table algorithms "by hand" and insert the following input 23, 68, 38, 75, 42, 53, 89, 91, 45 into a hash table of size 11. Keep the load factor ≤ 70% (except for quadratic probing that requires load factor below 50%). Rehash the table by increasing the size to 23 when the load factor exceeds the threshold. Show the resulting tables using different collision resolution strategies:

Separate chaining
Linear probing
Quadratic probing (remember to keep the load factor below 50\%)
Double hash with the second hash function h(x) = M - (x mod M), where M is the largest prime number smaller than the table size ( M = 7 when table size is 11; M = 19 when table size is 23

You need not write any code for this algorithm. Just submit diagrams of the resulting hash table state. Your diagrams should be similar to zyBook Figures 5.2.3 and Figures 5.3.8.

(This exercise prepared by Prof. Dulimarta.)

Using Hash Tables

Use this GitHub Classroom link to get started: classroom.github.com/a/UFwvldBk.

A polynomial is sparse if it has few terms relative to its max degree. For example, 15x^1000 + 23x^501 + 3x^2 + 2 would be sparse because all but four of the 1001 coefficients are 0.

To multiply two polynomials, you (1) multiply all pairs of terms, then (2) combine like terms.

One way to combine the like terms is to calculate all the terms, sort them (which could be slow), then combine them.
Another approach is to store the result in a hash table and combine terms as you go along.

Implement both methods (by completing Polynomial.hpp) and report which is faster and by how much. Specifically, choose several large inputs, time the both the fast and slow multiply algorithms and report the results. (Before running the tests, you may want to re-compile your code with the -O3 flag.)

(This is exercise 5.13 from the Weis text using starter code prepared by Prof. Dulimarta.)

Submission and grading

Submit the written problems in class.
Make sure all relevant code (including unit tests) is checked in to GitHub by the due date.
Place the code to be graded is on the master branch.
You are expected to fix and re-submit buggy code. Because your code will eventually be correct, your grade will be based primarily on timeliness.
There is a penalty for each buggy submission.

Updated Tuesday, 1 October 2019, 9:01 AM