22C:30, 22C:115 Project 2 Clarifications

Due date: Friday, 11/7, 5 pm

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.

Sriram Pemmaraju