In C$++$ language Week $15$ Project $3$: Hash Tables

As a reminder, submit both Part One and Part Two in the same word document.

Part One:

Create three programs to store last names. Each program should be submitted in a word document on separate pages. The three programs you should create are listed below

name, b$)$ Search for a name, or c$)$ Exit. After each successful operation a new menu is displayed and the user can take the next action.

a$.$ If the user selects Enter a Name, then the program will ask for user input and assign it to the next available spot in the array.

b$.$ If the user selects Search for a Name, then the program will ask for the name to search and then conduct a sequential $($one after the other until found$)$ search of the array from location array$[0]$ to array$[$last

entered$].$ If the name is not there the program returns "name not in data base".

c$.$ If the user selects Exit, the program terminates.

The second of the programs will store the input name into a sorted linked list. The menu will be posted as in step one above.

a$.$ If the user selects Enter a New Name, then the user is prompted for the name and then the program goes through the linked list and inserts the name in the appropriate position. The program will maintain

a count of the items in the list and will also keep an additional header pointer that points to the middle $($alphabetically$)$ of the list.

b$.$ If the user selects Search for a Name, then the user is prompted for the name to search and the program will then see which side of the midpoint it is on and either start the search from the beginning and

end when found or at the midpoint or start from the midpoint and finish when found or at the end. More specifically the search can terminate once the name is outside the alphabetically sorted area so for

example if searching for the name Roberts the search can conclude either if it is found or the name say...Rylie is encountered because it is outside the search area.

c$.$ The exit function stops the program or the new menu is displayed.

predetermined based on a user selected size try $5,10,15,20.$

a$.$ If the user selects Enter a New Name, they will be prompted for the name. The program will then add up the ASCII codes of the letters in the name and obtain a sum. Then they will take the sum modulo

array size to obtain the array index. Then they will go to the linked list for that array index and insert the name in that linked list as per the rules in step $2$ above. The key idea here is to keep the linked lists

small...to do that make the array sufficiently big so as to spread the names out. Experiment with different array sizes to optimize your program.

b$.$ If the user selects Search for a Name, then enter the name and compute the hash as before. Use the hash as the index into the array, then search the linked list at that location as in program $2$ above. Notice

that if the linked list header points to null then the item is not found. How cool is that!

c$.$ If the user selects Exit, the program terminates.

draw graphs of the number of times the inner most loop of instructions is called for both the insert and search routines for each program.

should count the number of times that routine is reached by incrementing it$.$ Then print the counter each time the code is run along with the count of how many names are in the list$/$array$/$hash table.

Part Two:

Answer the questions below:

Which method has the fastest input routine $($in terms of the counter$)?$

Which method has the slowest input routine $($in terms of the counter$)?$

Which method has the fastest search routine $($in terms of the counter$)?$

Which method has the slowest search routing $($in terms of the counter$)?$

and write a one page summary of their uses.