22C:30, 22C:115 Homework 3

Due date: Monday, 11/17

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{
		// 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();
		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.

  1. What sort of a function do you see?
  2. Explain in 2 sentences the rate of growth of this function.
  3. 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 "+".