Midterm Exam, 10/17 Thursday

Notes: (i) There are 5 problems, each worth 40 points, for a total of 200 points. (ii) This is an open notes exam. (iii) You have 50 minutes to finish the exam. Even though all problems are worth the same, they are not equally challenging. So allocate your time wisely.

  1. Consider the hash function we discussed in class and implemented as part of the ChainingHashTable class. This hash function took a string s = (sn-1, sn-2, ..., s1, s0) and returned an integer in the range [0, M-1], where M is the size of the table, using the following formula:
    h(s) = value(sn-1) 64n-1 + value(sn-2) 64n-2 + ... + value(s1) 641 + value(s0) 640.
    Here value(si) refers to the ASCII value of character si. Suppose we use a table of size M = 64. Write down ten 4-letter strings, all of which hash to the same slot.

    Note: You don't need a calculator to solve this problem. In fact, you don't have to do much of a calculation to solve this problem.

    Answer: aaaa, baaa, caaa, daaa, eaaa, faaa, gaaa, haaa, iaaa, jaaa

    Common Errors: Some students felt that strings that are obtained by permuting the characters (e.g., abcd and bcda) would hash to the same slot. This was true of an earlier hash function we had discussed in class. For the hash function given here, with M = 64, its value is exactly equal to the value of the last (rightmost) character in the string. This is because in the given hash function the values of the remaining characters are multiplied by powers of 64 and hence their contribution to the hash value is a multiple of 64. Therefore when we take remainder with respect to M = 64, the the total contribution of the remaining characters is 0, leaving only the contribution of the rightmost character.

  2. In many applications (e.g., transportation) the edges of a graph have associated weights. For example, an airline might be interested in maintaining a graph whose vertices are US cities and whose edges represent single-hop flights that the airline runs. The airline might want to associate with each edge (e.g., {Chicago, Dallas}) a quantity such as the distance in miles or travel time between the endpoints of the edge.

    Think about the adjacency matrix representation of a graph.
    (a) Where would you store edge weights in such a representation (answer in one sentence)?
    (b) Give an example of a method in the myGraph class whose signature (i.e., the first line of the method that specifies name of the function, return type, arguments, etc.) would have to change as a result of edges having weights? What would be the new signature be?

    Answer: (a) The edge weights could be stored in a triangular 2-d array, let us call this EdgeWeights, that would correspond to the boolean adjacency matrix Edge that we currently use in the sense that Edges[i][j] will tell us if edge {i, j} exists and EdgeWeights[i][j] will tell us the weight of this edge.
    (b) We would have a new method with signature,

    	void addEdge(String u, String v, WeightType w)
    either instead of or in addition to the method
    	void addEdge(String u, String v)
    that the class currently contains. Here WeightType is whatever type the user expects the weights to be (e.g., int, float, double, etc.).

  3. Consider the following method that I want to add to the StringLinkList class.
    	void mystery(){
    		StringLink newFirst = first;
    		while(first.next != null){
    			StringLink temp = first.next;
    			first.next = temp.next;
    			temp.next = newFirst;
    			newFirst = temp;

    Suppose that the above mystery method is applied to a StringLinkList object containing three strings, "a", "b", and "c" in that order. Show how this StringLinkList object changes as the method executes. Specifically, show the structure of the StringLinkList object immediately after each execution of the statement newFirst = temp;. Make sure you show exactly where temp, first, and newFirst are pointing.

    Answer: After the first line (newFirst = first;) is execute the object looks like:

    		a | ---> b | ---> c ---> null
    with first and newFirst pointing to the link containing a.

    After the 1st iteration of the while-loop (i.e., after newFirst = temp has been executed):

    		b | ---> a | ---> c ---> null
    with newFirst and temp pointing to b and first pointing to a.

    After the 2nd iteration of the while-loop (i.e., after newFirst = temp has been executed):

    		c | ---> b | ---> a ---> null
    with newFirst and temp pointing to c and first pointing to a.

    The while-loop ends after the execution of this statement since now first.next == null.

  4. I want to make the StringLinkList class implement the Comparable interface so that pairs of StringLinkList objects can be compared. Here are rules (that I made up) to tell us which StringLinkList object is smaller, given a pair of StringLinkList objects: Use these rules to implement the compareTo method for the StringLinkList class.


    	// Assumes that givenList is not null, though it may be empty
    	int compareTo(StringLinkList givenList)
    		// Check is the givenList is empty
    		if(givenList.first == null)
    			// both lists are empty
    			if(first == null)
    				return 0;
    			else // this list is "larger"
    				return +1;
    		// this list is empty
    		else if(first == null)
    			return -1;
    		// both lists are non-empty, so we just compare the strings
    		// in the first links
    		return compareTo(first.sData, givenList.first.sData);

    Common Errors: Many students felt that they could change the signature of compareTo to whatever is convenient, forgetting that compareTo has to have exactly the syntax and semantics defined for it in the Comparable interface. This means that it has to return an int, has to have exactly one StringLinkList argument, etc.

  5. You are given a 2-dimensional integer array A of size n × n and you are told that the integers in each row are in increasing order and the integers in each column are in increasing order. Your task is to search for a given integer x. Describe in 2 sentences how you would use the ordering of the rows and columns of A to "speed up" your search for x.

    Answer: Compare the given element, say x, to the element in the middle of A (i.e., to A[n/2][n/2]). If x equals this element, we have found what we were looking for; if x is greater than the middle element of A, we can ignore the top-left one-fourth of A and search in the remaining three-fourth; if x is smaller than the middle element of A, we can ignore the bottom-right one-fourth of A and search in the remaining three-fourth.

    Common Errors: Many students assumed that the description of the 2-array given in the problem, implied that the first element of row 2 is larger than the last element of row 1, the first element of row 3 is larger than the last element of row 2, and so on. However, this need not be the case and the matrix may look like:

    	1 	20 	50
    	15	20 	105 
    	16	77	106
    With this structure it is not possible to do one binary search on a row, find an appropriate column and then do one binary search on that column.