22C:21 Midterm Exam

Date: Friday, 3/3

Notes: This is an open notes/book exam. It will be graded out of 200 points (20% of your grade) and each problem is worth 50 points.

  1. 	i = n;
    	while(i > 0)
    		if(binarySearch(list, i))
    In the above code fragment, list is a sorted int array of size n and binarySearch is a boolean function that performs binary search for i on the array list and returns true if i is found; false otherwise.

    What is the running time of the code fragment shown above, as a function of n. Express your answer in Big Oh notation. Carefully show the steps you went through in deriving your answer.

    Solution: The worst case running time is O(n log n). This is because the while-loop executes n times and in each execution takes O(log n) time, in the worst case. O(log n) work in the worst case, repeated n times is O(n log n) work in the worst case.

    Common errors: Most of you correctly noted that each call to binarySearch in the above code takes O(log n) time. However, some of you stopped at this. Some of you attempted to go further, but got O(n) or O(n^2) instead.

  2. Write a method of the LinkList class that deletes and returns the last Link of the linked list. Use the following function header:
    	public Link deleteLast()
    If the linked list is empty, then the function just returns null.

    Solution: Here is the code.

    	public Link deleteLast()
    		// if list is empty
    		if(first == null)
    			return null;
    			Link current = first;
    			Link previous = null;
    			while(current.next != null)
    				previous = current;
    				current = current.next;
    			// if list has one element, first needs to be	
    			// updated
    			if(previous == null)
    				first = null;
    				previous.next = null;
    			return current;

    Common errors: Many of you forgot to update first when the list has one item. Some of you assumed that the linked list is doubly linked and that there was a reference called last to the last item in the linked list. Some of you reached the last Link correctly, but had trouble deleting it. For example, in some answer books, I saw previous = null as an incorrect attempt at deletion.

  3. Write a method of the myGraph class that determines if a given pair of vertices have a common neighbor. The function returns true if the given vertices have a common neighbor; otherwise it returns false. Two vertices A and B have a common neighbor if for some vertex C, the graph contains the edge between A and C and the edge between B and C. The function is partially given below, you just have to supply the missing code. For simplicity, I have assumed that the two given vertices are present in the graph.


    	public boolean haveCommonNeighbor(String vertex1, String vertex2)
    		int id1 = getIndex(vertex1);
    		int id2 = getIndex(vertex2);
    		for(int i = 0; i < numVertices; i++)
    			// Check if i is a neighbor of both
    			// id1 and id2
    			boolean check1 = false;
    			boolean check2 = false;
    			if(i <= id1)
    				check1 = Edges[id1][i];
    				check1 = Edges[i][id1];
    			if(i <= id2)
    				check2 = Edges[id2][i];
    				check2 = Edges[i][id2];
    			return (check1 && check2);
    		return false;
    Common Errors: Many of you ignored the triangular structure of the 2-dimensional boolean array Edges and checked Edges[id1][i], Edges[id2][i], etc. without paying attention to the relative values of i, id1, and id2. Some of you wrote correct but extremely inefficient solutions if which you got the list of neighbors of vertex1, list of neighbors of vertex2, and then checked if the two neighbor lists had a common element. Such solutions also typically ignored the fact that you had to just supply the missing code and not write the function from scratch.

  4. Consider the STRANGE_QUEUE ADT that is similar to the QUEUE ADT, except that each item has an associated priority that can be 0 or 1. Items with priority 0 are considered very important and are "served" before items of priority 1. Like the QUEUE ADT, the STRANGE_QUEUE ADT also supports the operations insert and delete, but these operations for the STRANGE_QUEUE ADT pay attention to the priority of the items. Here is a description of how insert and delete work for the STRANGE_QUEUE ADT.

    Write a brief description (5-6 lines) of how you would implement the STRANGE_QUEUE ADT so that the insert and delete functions, both run in O(1) time. Your description would have two parts: (1) describing the data structures you will use for your implementation and (2) how the two operations are implemented, using these data structures.

    Solution: We should keep two separate regular queues, one exclusively for items with priority 0 and another for items with priority 1. So the data members could just be:

    	private Queue q0;	
    	private Queue q1;	
    Any implementation of the Queue class that performs insert, delete, and isEmpty in O(1) time will suffice for our purposes.

    The insert operation inserts the given item into q0 if it has priority 0 and into q1 if it has priority 1. The delete operation checks if q0 is empty first. If it is non-empty, then it deletes an item from q0 and returns it. If q0 is empty, it deletes an item from q1 and returns it, assuming that q1 is non-empty.

    Common errors: Many of you wrote solutions that performed the operations correctly, but not in O(1) time per operation. Some of you had more exotic and incorrect solutions such as using hash tables, etc.