Problem Set 3. Posted 2/2

1. Using this implementation of the Graph class, I want you to write a program that builds a graph called the Ladders graph. Later we will use the Ladders graph to play the Ladders game. In this two-player game, one player chooses a starting word and an ending word and the other player constructs a "ladder" between the two words. A ladder is a sequence of words that starts at the starting word, ends at the ending word, and each word in the sequence (except the first) is obtained from the previous word by changing a letter in a single position. For example, suppose the starting word is flour and the ending word is bread, then a ladder between these two words is: flour, floor, flood, blood, brood, broad, bread. Here is the link that will take you to a file called words.dat that contains 5757 five letter English words. This word list comes from Stanford Graphbase, a collection of interesting data sets and graph algorithms put together by Donald E. Knuth. The original file can be found here. This word list is the database that your program will use to construct the Ladders graph. The Ladders graph should contain a vertex for every word in the file and an edge between every pair of vertices that differ in exactly one position. To construct the graph, you should call the function addVertex on every word in the file and then the function addEdge for every edge you want to add. After you have constructed the Ladders graph, I want your program to answer the following questions:
   • What is a word with maximum number of neighbors? Output such a word and all its neighbors.

   • What is a word with fewest number of neighbors? Output such a word and all its neighbors.
   What to submit: You will have to electronically submit this program in a file called Ladders.java. I will open a directory called homework3 for this purpose. There is no need to submit the Graph class.

2. Write a 0-parameter member function of the LinkList class called reverse, that reverses the linked list on which it operates. There is no reason to ask for any new memory, so write the function i without any use of the new operator.

3. The adjacency list representation of a graph stores adjacencies, not in a 2-dimensional boolean matrix, but in an array of linked lists. Suppose that the vertex Boston has three neighbors, Chicago, Cleveland, and Baltimore. Further suppose that Boston appears in slot 5 in the String array names. Then slot 5 in Edges would contain a linked list with Chicago, Cleveland, and Baltimore, in some order.

   Implement a new myGraph class that uses the adjacency list representation rather than the adjacency matrix representation. The only public methods you are required to implement are the the two constructors, addVertex, and addEdge.

   Notice that the linked list mentioned above contains strings. This means that the Link class and the LinkList class have to be modified slightly.