Final will be Friday, May, 13th in the morning 911:30 am in Phillips 101.
The final is cumulative, and is a closed notes, closed book test!
Those with 3 finals in one day should let us know ASAP, by sending email to eva@cs.cornell.edu.
We will rearrange office hour for the week to help prepare for the final. Please check the Web for the schedule.
The topics for the prelim cover the material from
Nothing will be tested that we did not have in class or homeworks. So your notes from class and the homework is a better guide than the book. You need to know all topics covered by the two prelims.
Here I only provide a list for the topics that we covered since prelim 2.
For practice questions, you should know all questions on the prelims, and all homeworks. Use the practice questions suggested in the previous prelim review sets. The book has many excellent additional questions after each sections, and also at the end of each section. Feel free to ask us about any of them in office hours. Here I will only suggest additional review questions for the topics we covered since prelim 2.
Following table gives the correspondence between the question numbers in the edition five of the book and edition four of the book. If the edition four question number contains a  mark, the question is reproduced in this PDF file and this PS file.
Review Questions for the Topics since Prelim 2 
Question in 4th edition 
Question in 5th edition  Statement of the question 
Chapter 5 in edition V or Chapter 4 in edition IV 

  Review 11  a) What does it mean to say that a random
variable has a geometric distribution with probability p? b) What is the mean of a geometric distribution with probability p? 
21  12  
  Supplementary 28  Use Chebyshev's Inequality to show that the probability that more than 10 people get the correct hat back when a hatcheck person returns hats at random does not exceed 1/100 no matter how many people check their hats. (Hint: Use Example 6 and Exercise 35 in Section 5.3) [Please look at these examples and exercises from the book] 
  31  There are n different types of collectible
cards you can get as prized when you buy a particular product. Suppose
that every time you buy this product it is equally likely that you get
any these of these cards. Let X be the random variable equal to the
number of products that need to be purchased to obtain atleast one of
each type of card and let X_j be the random variable equal to the number
of additional products that must be purchased after j different cards
have been collected until a new card is obtained for j=0, 1, 2,..., n1. a) Show that X=\sum_{j=0}^{n1}X_j. b) Show that after j distinct types of cards have been obtained, the card obtained with the nest purchase will be a card of a new type with probability \frac{nj}{n}. c) Show that X_j has a geometric distribution with parameter \frac{nj}{n}. d) Use parts (a) and (c) to show that E(X)=n\sum_{j=1}^{n}1/j. e) Ust the approximation \sum_{j=1}^{n}1/j \approx \ln(n)+\gamma where \gamma=0.57721... is Euler's constant, to find the expected number of products that you need to buy to get one card of each type if there are 50 types of cards. 
  Section 5.3 exercise 30  
Assume H is a class of hashfunction that maps
a set U to integers 0 ≤ i < p for some prime p. We say that a Hash
function class H is 2universal if for any two elements u,v in U, and any
two integers i,j in the above range, the probability that for a randomly
chosen hash function h in H, we get h(u)=i and h(v)=j is exactly the same.
Note that randomization here is over the selection of h in H, and the
values i, j and items u, v are given. (a) Show that the above probability must be 1/p^{2} for all 2universal hash function classes. (b) Assume that the universe is a sequence of integers x=(x_{ 1},...,x_{ r}) where each x_{i} is in the range 0 ≤x_{ i} < p, as we had in class. Recall the class we defined in class, where hash functions are of the form h(x)=(S_{i.} a_{i}x_{ i}_{.}mod p) with the values a_{i }chosen independently uniformly at random. Show that this class is not 2universal. (c) Show that the class h(x)=(S_{i.} a_{i}x_{ i.}+b mod p), where the values a_{i }and b are chosen independently uniformly at random is 2universal. (d) Consider the following use of 2universal hashfunctions for authentication. Alice and Bob want to send messages over email, and agree on the following authentication scheme. They have in mind a 2universal set of hashfunctions (such as the one in part c above), and select a function h in this class that they keep secret. When sending a message m, they add an authentication tag t=h(m). Suppose Eve (who is an eavesdropper), interrupts the message (m,t), and would like to replace m with a different message m'. However, she does not know the proper tag t'=h(m'). Show that the probability that Eve can select the tag t' correctly (so that t'=h(m')), assuming she knows m, m', t (which satisfies t=h(m)), and also the class H of 2universal hashfunctions Bob and Alice used, but does NOT know the secret function h is 1/p. 

Chapter 8 in edition V or Chapter 7 in edition IV 

Review 11  Review 11  
39  Supplementary 39 

5051  Supplementary 5051 

  Section 8.4 exercise 14 

Section 7.4 exercise 14  22 

29  37 

Section 7.4 exercise 12  Section 8.4 exercise 20 

Section 7.8 exercise 1920  Section 8.8 exercise 2122 

Chapter 9 in edition V or Chapter 8 in edition IV 

Supplementary 11  Supplementary 11  
 
Section 9.4 exercise 21  
 
42 