Background
CS 61B, MT2 Version B, Spring 1999
CS 61B, Spring 1999 MT2 Version B Professor M. Clancy
Some of the problems on this exam involve intevals of integers. (Note the difference between these intervals and thsoe you worked with in homework assignment 4, which represented intervals on the real number line.)
The interval [a,b] represents all the integers that are greater than or equal to a and less than or equal to b. For example, [3,5] represents the set of integers {3, 4, 5}, [-5,-4] represents the set {-5,-4}, and the interval [5,3] represents the empty set.
The Interval class is defined as follows. public class Interval {
private int myLeft;
private int myRight;
Constr/u/ctor.
public Interval (int left, int right) { … }
Return//this’s left endpoint. public int left ( ) {
return myLeft;
}
Return//this’s right endpoint. public int rightt ( ) {
return myRight;
}
Retur/n/a hash value forthis. public int hashCode ( ) { … }
Retu/rn/ exactly whenthis represents the smae interval asintvl. public boolean equals (Interval intvl) { …
}
// Returntrue exactly whenthis contains x. public boolean contains (int x) { …
}
Retur/nt/rue whenthis overlapsintvl, i.e./c/ontains integers in common withintvl.
public boolean overlaps (Interval intvl) {…
CS 61B, Spring 1999 MT2 Version B Professor M. Clancy 1
}
CS 61B, MT2 Version B, Spring 1999
Retu/r/n the result of combiningthis withintvl. Preco//ndition:overlaps (intvl).
public Interval extendThrough (Interval intvl) { …
} }
Problem 1 (4 poinst, 10 minutes)
The hash function below, a variation on the PCC function from “Real-World Hash Functions,” is intended to be applid to English words as was the function in homework assignment 7. There are at least two sets of table sizes for which the function will work badly. Name them, and briefly explain your answers.
Suppose for the purposes of this problem that the Interval class from homework assignment 4 is defined as follows:
public int hashCode ( ) {
int h = 0;
for(int