When working with larger codebases, it is easy to get overwhelmed. Any obstacles encountered, no matter how small, can seem insurmountable. Our first task is to modify the Makefile for our project. This will make it simple to compile our project and test the different components we will be adding.

Feel free to use the example we did in class or the cookbook from makefiletutorial.com to get started.

Tasks

Modify the Makefile with the following targets:

release: Builds the full project normally. The executable should be placed in a build directory.debug: Builds the project with the flags $-$g $-$Wall.

Verify that your Makefile works by building the project and running it $($requires all tasks complete$).$

Collision Resolution using Quadratic Probing

One flaw of linear probing for collision resolution is that samples tend to cluster together in different parts of the map. An alternative open addressing scheme that does not suffer from clustering is quadratic probing.

Quadratic probing computes a new index based on the result of a hash function and quadratic function. Let h$($k$)$ be the original hash function. The new index is computed as

h$($k$,$i$)=($h$($k$)+$c$1$i$+$c$2$i$2)$mod$$n$.$

Complete the function int quadratic$\_$probe$($int hash, int i$,$ int n$,$ int c$1,$ int c$2)$ that computes the function above. The input arguments are:

int hash $-$ The original hash value computed by the hash function.

int i $-$ The parameter i as described above.

int n $-$ The size of the hash map.

int c$1-$ The first coefficient of the function.

int c$2-$ The second coefficient of the function.

This function will also allow you to explore the effects of changing the coefficients c$1$ and c$2.$ In most cases, you might use a default implementation where c$1=$c$2=1.$ For this case, create a macro that defines a function call default$\_$probe$($hash$,$ i$,$ n$)$ to call the function quadratic$\_$probe$($hash$,$ i$,$ n$,1,1).$

Add these functions to hash$\_$map$\_$utils.$($c$|$h$).$ The macro definition should be placed after the declaration in hash$\_$map$\_$utils.h$.$

Tasks