22C:21: Computer Science II: Data Structures

Midterm. 10/19. 10:30-11:20 am

Notes: The midterm is open notes and books. However, please do not use your laptops. The exam is worth 200 points, 60 each for Problems 1 and 3, 80 for Problem 2.

Problem 1.
Your boss wants you to implement an ADT that she calls the RANGE ADT that maintains a collection of real numbers and supports the operations:

Your boss also tells you a few more things about how your implementation will be used. It is expected that your implementation of the RANGE ADT will start by reading from a large data file containing millions of real numbers and storing this data in appropriate data members. All of this is expected to happen in a constructor and it is expected that the constructor will be a bit slow, since it has to read a lot of data; however the operations themselves have to be fast since they are called repeatedly. It is also expected that the delete operations are very rare relative to the rangeSize operations. Thus it is critical that the rangeSize operations be extremely fast, whereas it is ok for the delete operations to be relatively slow. Answer the following questions based on this information.

  1. State the data members of the class range that implements the RANGE ADT. Describe the purpose of each data member, in one sentence. 
    	// stores the collection of real numbers in sorted order and is created and
	// filled in the constructor
	float[] collection; 

	// keeps track of the number of reals in the collection
	int numReals;
    Based on the data members you have chosen, describe in one sentence each how you would implement delete and how you would implement rangeSize.
    • delete(x): perform a binary search for x in collection and if x is found in slot j in collection, then all elements in collection[j+1..numReals-1] are shifted up one slot each.
    • rangeSize(x, y): perform a binary search for x and for y, obtaining indices i and j respectively; then return j - i + 1 if y is found and j - i if y is not found.
  2. What is the worst case running time of the two operations, delete and rangeSize as a function of n, the number of elements in the collection. Just state the running time, no explanation is needed.
    • delete(x): n
    • rangeSize(x, y): log(n)

Problem 2.
You send off your implementation of the range class to your boss, who returns in a few days and tells you that there is a problem. The implementation is meant to be running on cell phones and there is just not enough memory. She also gives you three pieces of additional information:

You go back to your desk, think about the problem, reimplement the class range, and send her a new implementation. She is thrilled with your new implementation because it has managed to save a huge amount of space and rangeSize now runs in constant time and delete is also much faster. You get amply rewarded for your fantastic work! Answer the following questions based on this information.
  1. State the data members of the new class range that implements the RANGE ADT. Describe the purpose of each data member, in one sentence. 
    // Keeps track of the number of reals in the collection that belong to each range, 
// [1000, 1000] (1000, 1001) [1001, 1001] (1001, 1002), [1002, 1002],...,(1999, 2000), [2000, 2000]
// and therefore will have size 2001.
int[] numRealsInInterval;
  2. Based on the data members you have chosen, describe in one sentence each how you would implement delete and how you would implement rangeSize.
    • delete(x): If x is an integer, then decrement the slot corresponding to x by 1, otherwise decrement the slot corresponding to (floor(x), ceiling(x)) by 1.
    • rangeSize(x, y): Sum up and return the values in numRealsInInterval in slots starting from the one corresponding to x to the one corresponding to y.

Problem 3.
For this problem, suppose that Darth Vader (or some other equally villainous character) has tampered with our implementation of the Queue ADT. When you perform a dequeue operation, you don't get the first element from the queue; instead you get the second element. Of course, if the queue has only one element, then that is what you get when you perform a dequeue. Using the Queue ADT, so maliciously tampered by Lord Vader, perform breadth first search on the graph shown below, starting from vertex A. Feel free to consult the code for breadthFirstSearch in the class myListGraph. For this traversal, show the following pieces of information:

  1. the order in which vertices are discovered by breadth first search,
    A, B, C, D, G, E, F
  2. the contents of the queue being used by breadthFirstSearch, after each enqueue operation, 
    	A
	B C
	B D G
	B G E
	B E F
	B E
	B
  3. and the breadth first search tree. 
    	A
       / \
      B   C
         / \
        D   G
       /     \
      E       F
Make sure that your queue is labeled so that it is clear where the front and the back of the queue are. Just to keep the traversal unambiguous, assume that the getNeighbors method returns the neighbors of each vertex in alphabetical order of their names.

graph 1