**Problem 1**

In Homework 2, one of the problems required constructing the `graph` class.
See Homework 2 Solution for my implementation of the `graph`
class. For this problem, you are required to add the `bfs` function to the graph
class. The function should have the following signature:

void bfs(const string & source, vector<int> & distances, vector<int> & parent);The vector

As a test of your implementation of `bfs`, use the `ladder` program and the
input file `words.dat` from Homework 2 to construct a graph of 5-letter words whose
edges connect pairs of words that differ in exactly one letter.
Then, by calling `bfs` find the 5-letter word that is farthest from the
word `about` in the graph and is still reachable from it.
Output a shortest path from `about` to this farthest word along with the number of
hops in this path.

Submit your new `graph` class containing the implementation of `bfs`,
your new `ladder` program, and a printout of the output mentioned in the
previous paragraph.

**Problem 2**

In class, we saw that the `queue` data structure provides the operations
`enqueue`, `dequeue`, and `isEmpty`.
Implement a `queue` class that provides member functions for these operations.
Use the following header for the queue class:

template < class T > class queue{ public: // inserts item at the back of the queue void enqueue(const T & item); // deletes and returns the item at the front of the queue T dequeue(); // indicates if the queue is empty bool isEmpty(); private: node < T > * front; };Note that the

To test your implementation of the `queue` class and to understand its (in)efficiency
write a program that enqueues integers 1, 2,...,n in that order in a queue.
Time your program and add output statements so that it reports the total amount of
time it takes to complete *all* n enqueue operations.
Let the value of n vary as 1000, 2000, 3000,...., 10000.
So your program should output the time it takes for 1000 enqueue operations,
2000 enqueue operations, 3000 enqueue operations, and so on.
Plot these times as a function of n.

- What sort of a function do you see?
- Explain in 2 sentences the rate of growth of this function.
- Explain in 2 sentences how to modify the above class, so that the
`enqueue`operation takes O(1) time.

You can download a simple and useful "timer" class from here and insert calls to member functions of this class in your program to time parts of your code.

Submit (i) the implementation of the `queue` class, (ii) your "timed"
program that enqueues elements repeatedly, (iii) your timing plot, and (iv) answers
to 3 above questions on the plot.

**Problem 3**

Write a recursive function to compute the binary equivalent of a given positive integer n.
The recursive algorithm can be described in two sentences as follows.

Compute the binary equivalent of n/2. Append 0 to it if n is even; append 1 to it if n is odd.Use the following header for the function:

string binaryEquivalent(int n);To append a "0" or a "1" to a string, you should use the string concatenate operation "+".