- The
`hashTable`should be defined as an`apvector`of`node <string>`pointers. - For Project 2 make your own
`graph`class, starting from the one you made for Homework 2. This means that you will also have to submit`graph.h`and`graph.cxx`. - For Project 2, you can use the STL
`queue`class. - In the handout I defined h(s) = D(s) mod M. If s is very long, then D(s)
may be a very large integer and because of integer overflow D(s) may have
the wrong value. Here is an illustration of how to get around this problem.
Suppose that the string s = abcd. Then D(s) can be written as
D(s) = 26 (26 (26 (a') + b') + c') + d'

where a', b', c', and d' are the ASCII values of a, b, c, and d respectively. From this observe that D(s) can be computed in a loop, such that in each iteration the current value of D(s) is multiplied by 26 and the ASCII value of the next letter is added. You can get around the integer overflow problem by taking "mod M" at the end of each iteration rather than after D(s) has been completely computed. It is not hard to show that D(s) computed in this manner will be identical to D(s) computed by taking "mod S" once at the end, after D(s) has been completely computed. -
For the part of the project where you have to generate replacements, a few of
you have noted that if you construct the entire graph of strings
explicitly, it will take up too much memory and too much time. But there is
no reason to explicitly construct the graph. The graph is known to you implicitly
by the fact the vertices correspond to strings and edges connect pairs of
vertices according to the 4 rules in the handout. The
`kNeighborhood`would still be a bfs, but on an implicitly specified graph. The main difference would be that the function`getNeighbors`used by bfs would return the neighbors of a vertex, not by scanning the adjacency list of a vertex, but by generating the neighboring strings by applying the four rules.