Hash Table with Chaining for Phone Number Word Representation Project

This assignment requires the implementation of a hash table with chaining to convert phone numbers into word-based representations. The program should take a 10-digit phone number as input and output its word-based equivalent, if one exists, considering various possibilities for 10, 7, 3, and 4-digit word representations. The solution involves creating a hash table of prime size M, using a specific hash function, and handling collisions through chaining. The program must handle cases where a full 10-digit word representation is available, followed by 7-digit, 3-digit, and 4-digit representations, printing all possible word combinations. The assignment includes requirements for pseudocode, runtime analysis, and code testing. The hash table should be dynamically resized using rehashing if collisions become excessive. The solution should effectively search for word representations based on the given phone number and the words stored in the hash table.

Assignment 2 Due at 11:00 AM on November 22, 2016
(100 pts)
Objective: You will implement hash table with chaining.
The international standard letter/number mapping found on the telephone is shown below:
Using these characters on the key-pad, we can come up with word-based representation of a
phone number so that it would be easy to remember. For example, 1-800-AAA-HELP. This is
very much easy to remember than 1-800-222-4357. It is obvious that some phone numbers
cannot be turned into word-based representation. For example if the number has 1 or 0,
then there is no corresponding characters on the key-pad. Some time we may not find
meaningful word to represent the given number even if it does not contain 0 or 1. In this
project, you will write a program that will ask user to enter a phone number (10-digit
excluding leading 1) and will print out the word-based representation if exist otherwise it will
indicate that there is no meaningful word-based representation of the given number and just
print out the given number in the following form: 1-area-exchange-number.
A typical phone number has three components:
1) area (three digit)
2) exchange (three digit)
3) number (four digit)
As you have seen in the example above, if one wants to find out the word-based
representation of a given phone number, he/she will find the word based representation of

exchange and number i.e. last 7-digit of the given phone number. There are several
possibilities here:
1) If there is only word-based representation of whole 7 digits
2) Else If there is only word-based representation of exchange (3 digit) and number (4
digit)
3) Else If there is word-based representation of only exchange (3 digit)
4) Else If there is word-based representation of only number (4 digit)
5) Else there is no word-based representation given number.
Hence your program should do the following:
1) If there exist 10-digit word-based exist, then print it (or all if more than one).
2) If there exist 7-digit excluding area code, then print out it (or all if more than one).
3) If 7 and 10 are not possible, then print 3-digit followed 4-digit form. Again print all
possibilities.
4) If step 1, 2, and 3 are not possible, then print only the exchange in a word-based
form.
5) If step 1, 2, 3, and 4 are not possible, then print only the number in word-based form.
6) If none is possible, then print the number in 1-area-exchange-number form.
Examples:
1) Given number is 2266762559, then your output should be:
1-ABNORMALLY
2) If the given number is 2702637422, then your output should be:
1-270-AMERICA.
3) If the given number is 6157862243, then your program should print out the following
numbers:
1-615-RUN-ACHE
1-615-RUN-ACID
There is no meaningful word for 7862243. So we look at the words for 786 and 2243.
These are RUN, SUM, SUM and ACHE, ACID, CAGE. The all possible are listed as
above.
4) If the given number is 1939292244, then it returns/lists the following phone number:
1-193-WAX-2244
1-193-WAY-2244
5) If the given number is 18003218428, then it returns/lists the following phone number
1-800-321-THAT
6) If the given number is 18002002244, then it returns/lists the following phone number
1-800-200-2244

Here is what you need to solve this problem:
1) You are going to create a hash table of size M>=10000 and M is a prime number.
2) This table is array of a following object:
3) You will fill this table with words of length 10, 7, 4, and 3 using the following hash
function:
h(K)= ⌊ M (KA mod 1) ⌋, where A= √ 5−1
2
4) Let us determine what is K in the above function: Assume that 10-character word is
abbreviate. Using the table given above, we will get 2227384283. Assume that
M=5003. Then abbreviate will be inserted in the list of index 1106.
5) h(2227384283)=1106. So you will look at the KEY at index 1106 in the table. If KEY is
2227384283, Then abbreviate will be inserted in the list of index 1106. If KEY is -1,
then that linked list is empty. So KEY will 2227384283 and word abbreviate will be
inserted in the list of index 1106.
If there is another word, say a0 a1 … a9, and its 10-digit number, say x0 x1 … x9 , is
hashed into the same index as above, say 1106. Then you will check if x0 x1 … x9 is
equal to the KEY=2227384283. If it is then word will be listed in that link. Otherwise
you will rehash the table. That is, find new prime number M, which is at least twice
the value of the previous M. re insert all the words in the table again using new hash
function.
6) You will repeat these process for all words of length 10, 7, 4, and 3.
7) Suppose a 10-digit phone number K is given
a- First compute h(K)
If KEY=K in that index, then list all the words in that linked list
If KEY=-1, then there is no word of length 10
b- Take the last 7-dgit of the number, say K1 and compute h(K1)
If KEY=K1 at the index of h(K1), then list the word in that linked list
If KEY=-1, then there is no word of length 7
c) repeat for 4 and 3 and cross product
Documentation:
1) Write pseudocode
2) Determine the runtime of the your solution

What to bubmit:
1) Code to test.
2) Documentation.