7
for class on Tuesday Feb. 22, 2000
Please read
Section 3.5 of the Schneider and Gersting text
(but you've already read 3.5.2),
and be prepared to discuss the following:
Unaccountably, the company that Carol and Dilbert and Wally work for has grown to 100,000 employees. Suppose your job is to take the standard, alphabetical company phone book and convert it into Carol's handy form, and then provide an algorithm that she or her computer could use to quickly look up the name corresponding to the incoming phone number. How would you do this? You can use an array N for the names and an array T for the telephone numbers, so that, e.g., if N[957] contained "Wally" then T[957] would contain Wally's phone number. (Careful: the number 957 is nobody's phone number--it's just the index into the two arrays.)
In this class we will focus on the lookup algorithm.