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.
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.).
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 ---> nullwith 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 ---> nullwith 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 ---> nullwith 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.
Answer:
// 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.
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 106With 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.