CS 538 - Homework 6

                                                                                                                           CS 538
                                                                                                                           Spring 1999



                              Assignment 6


Date Due:  Tuesday, April 27

Reading:  Chapters 9, pages 282 - 290

Problems:

1.  Assume you are grading the final for CS 538 and there are 22 people in
the class. You assign grades randomly between 0 and 100. 

What (approximately) is the probability that two people get 
the same grade ? 

b. What is the probability that 3 people get the same grade ? 

2. Consider the discrete log hash function as given in figure 7.3, 
page 238 of the text. Let the values of p,q, alpha, beta be as in 
example 7.1 on page 240. 

a. What is the domain and range of h ? How many elements are in the domain ?

b. Propose a reasonable new hash function h* which extends the domain of h
to arbitrarily large inputs. Give a small example of how your hash
function would work on larger inputs. (You may use the ideas of section
7.5 here, but you will need to deal with decimal integers rather than bit
strings.)

Do three of the following four problems. 

3. Page 256, #7.2. 

4. Page 256, #7.4 

5. Page 256, #7.5 (a)

6. Page 280, #8.3