22C:30, 22C:115 Homework 2

Due date: Friday, 10/17

Problem 1
This past week we used the node class to define singly linked lists. The node class and the associated linked list toolkit are given in the files: listNode1.h and listNode1.cxx. Modify the node class and the linked list toolkit so that any node object can contain any type of information in its data field. To test your implementation of the templated node class, compile and execute the following program testNode.cxx that uses the templated node class. Submit printouts of (i) your templated node class and the new linked list toolkit and (ii) the output produced when testNode is executed.

Note:

I am assuming that your templated node class is defined in a file called "listNode2.h". You will notice that this file is included at the top of testNode.cxx.
You will also notice that the current node class and the linked list toolkit functions (as defined in listNode1.h) have all been defined within the namespace main_savitch_5. If leave this in your templated node class, then you will have to explicitly write
```
			using namespace main_savitch_5;
```

Problem 2
Implement a simple templated graph class using the adjacency list representation (as discussed in the lectures). Templating the graph class will allow the names of vertices to have arbitrary types (not just the string type). Use the following data members:

			apvector < node < T > > myVertices;
			int myNumVertices;
			int myNumEdges;

and define and implement the following member functions:

void addVertex(const T & name);
void addEdge(const T & name1, const T & name2);
node < T > * getNeighbors(const T & name) const;
int numVertices() const;
int numEdges() const;

To test your implementation of the graph class write a program, let us call it, ladder, that reads the words in the file words.dat, and constructs a graph whose vertices are the words and whose edges connect pairs of words that differ in exactly one letter. For example, the graph will contain an edge between the words "adapt" and "adept" because one word can be modified to obtain the other by simply replacing one letter in one position by some other letter. Add code to ladder so that after constructing the graph it reports the number of words with no neighbors, number of vertices with one neighbor, number of vertices with two neighbors, and so on.

Submit a printout of your graph class, the ladder program, and the information on number of neighbors mentioned above.

Problem 3
Write a recursive function that takes two positive integers n and k, k < n, and produces as output all subsets of size k of the set {1, 2, ..., n}. Submit a printout of your function and submit the output produced by this function when called with n = 8 and k = 4.