Problem 1
For hashing, it is certainly possible to use a function that
does not create collisions of words. (Recall that a collision occurs when
two words have the same hash number as assigned by the hash function.)
For example, we could write the
ASCII for each word and interpret it as a non-negative binary number to
get the conversion to a number. Then no two words would convert to the same
number. What are the problems with using this method of converting
a word to a number for use with an index?
Hint: what is the range of possible numbers, even if we assume all words
have less than 30 characters?
Problem 2
The greatest common divisor of two positive integers x and y, written
gcd(x,y), is the
largest integer that divides evenly both x and y. The greatest common divisor
could be 1, as it is for 15 and 28, could be the smaller of x and y,
as it is for 6 and 18, or could be in between, as it is for 12 and 44
(gcd(12, 44)= 4). An algorithm developed by Euclid to find the gcd
of two inputs is given below. By convention we always let x be the
smaller of the two inputs
Euclid's gcd(x,y) where x <= y
set m = x;
set n = y;
set r = the remainder of n divided by m (r is an integer < m, possibly 0)
while (r is not equal to 0) repeat
set n = m;
set m = r;
set r = the remainder of n divided by m;
end repeated instructions
the gcd is m
Let's try this algorithm on the three examples above.
Euclid's gcd (15, 28)
m = 15
n = 28
r = 13
within the while loop:
1st iteration: n = 15
m = 13
r = 2
2nd iteration: n = 13
m = 2
r = 1
3rd iteration: n = 2
m = 1
r = 0
while loop stops since r = 0
gcd is m = 1
Euclid's gcd (6, 18)
m = 6
n = 18
r = 0
while loop is not executed since r = 0
gcd is m = 6
Euclid's gcd (12, 44)
m = 12
n = 44
r = 8
within the while loop:
1st iteration: n = 12
m = 8
r = 4
2nd iteration: n = 8
m = 4
r = 0
while loop stops since r = 0
gcd is m = 4
Part a Write a recursive version of Euclid's gcd algorithm.
Part b Give an argument to convince someone that the algorithm stops, i.e. explain why the while loop eventually stops.
Extra Credit Give an argument to convince someone that the algorithm
gives the correct answer. A helpful fact is that y = q*x + r, for some
positive integer q and positive remainder r < x.
Therefore if some third integer z divides x and y evenly, it
must divide r evenly.
What do you think is the average running time of Euclid's algorithm
as a function of the magnitude of y? (The proof of the average running
time of Euclid's algorithm is hard -- take a "guess".)