**
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:**

**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.