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 distances should contain shortest path distances of all vertices from the source vertex. The vector parent should contain the index of the parent of each vertex in a bfs-tree rooted at the source vertex. More specifically, if a vertex x is stored in slot i in myVertices then distances[i] should contain the shortest path distance from the source to vertex x and parent[i] should contain the value j if the parent of vertex v in a bfs-tree is stored in slot j in myVertices.
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 queue data structure is being represented as a singly linked
list and we use the node pointer front to point to the first node in the
list. Since we don't have a pointer pointing to the back of the queue/list, each
enqueue operation involves traversing to the back of the list and inserting
an element there.
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.
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 "+".