Description
1. (5 Points) Read a file and hash the words:
Read a text file (Raven.txt from Canvas) and hash the words using the suggested
hash function from Levitin, page 269:
h ← 0; for i ← 0 to s − 1 do h ← (h ∗ C + ord(ci)) mod m,
where:
h is the computed hash value,
s is the length of the word being hashed,
ci
is the i
th character of the word,
ord(c) is the numerical value of character c in the alphabet in use,
C is a constant larger than every ord(ci), and
m is the modulus defining the size of our hash table.
We will take ord(c) to be the ASCII value of the characters in each word. Thus,
ord(c) ∈ {39, 65, 66, . . . , 90, 97, 98, . . . 122} for c ∈ {0
, A, B, . . . , Z, a, b, . . . , z},
respectively1
. All other characters are discarded; we define words as unbroken
sequences (strings!) of consecutive alphabetic characters, both upper and lower
case, plus apostrophes, in the lines read for the file. (In C++, the function
int(letter) returns the ASCII value of character ‘letter’.)
For our “Raven” text file, we will take C = 123 and m = 1000. These represent
parameters that can be changed to alter the shape and composition of our
resulting hash table. For now, we will use these values for the sake of consistency.
You are free to experiment with changing these parameters on your own, of
course!
1That apostrophe will introduce a couple of artifacts given our text file. Working with ‘real’
data gets messy. See if you can find the artifacts, but consider them unique words.
1
2. (10 Points) Create a Hash Table using Closed Hashing (Open Addressing):
a. Build a hash table of size 1000, i.e. entries from 000 to 999, from the hash
values computed in Part 1 above. Load them into the table in the order they
occur in the file, discarding duplicates. Our table will be far from full–you
needn’t worry about re-sizing it–we will examine the effects of its load factor
in Part 3 below.
b. Display the table, starting with table entry 0, in lines of the form:
Hash Address, Hashed Word, Hash Value of Word
(Remember, the Hash Address will not match the Hash Value when the resolution of a collision forces a word to be cascaded down the table. Also,
remember that the table should be thought of as a circular list so that a
word which cascades past the bottom end of the table gets wrapped to the
top in looking for an open place in the table.)
Note: Your program may perform Parts 1 & 2 simultaneously, if you wish.
3. (20 Points) Explore the Hash Table:
Add to your code routines that answer these questions. Some answers may not
be unique. You may resolve these issues by presenting either any correct answer
or all correct answers.
a. How many non-empty addresses are there in the table? What does that make
the load factor, α, for our table?
b. What is the longest empty area in the table, and where is it?
c. What is the longest (largest) cluster in the table, and where is it?
d. What hash address results from the greatest number of distinct words, and
how many words have that address?
e. What word is placed in the table farthest from its actual hash address, and
how far away is it from its actual hash address?
4. (25 Points) Implement Dijkstra’s Algorithm with weighted graphs like this:
Your code should read a text file and then ask for input from the console for
start and destination nodes and use Dijkstra’s algorithm to find the “length” of
the shortest path between them. It should also display the sequence of nodes
that constitute this shortest path.
You can assume the associated graph, read from a text file, is connected and
that the input file is consistent. (The main diagonal will consist exclusively of
zeroes, there will be no negative edges, etc.)
10
0 50 7 10 0 0 0 0 0 0
50 0 30 0 3 0 99 0 0 0
7 30 0 6 27 15 0 0 0 0
10 0 6 0 0 11 0 0 4 0
0 3 27 0 0 12 120 105 0 0
0 0 15 11 12 0 0 119 5 0
0 99 0 0 120 0 0 2 0 67
0 0 0 0 105 119 2 0 122 66
0 0 0 4 0 5 0 122 0 190
0 0 0 0 0 0 67 66 190 0
A(0) M(2)
R(3)
J(1)
K(4)
S(5)
N(7)
T(8)
I(6)
D(9)
7
10
50 30
3
99
6
27
15
11
4
12
105
120
119
5
2 67
66
122 190
