Final will be Friday, May, 13th in the morning 9-11: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 at-least 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,..., n-1. a) Show that X=\sum_{j=0}^{n-1}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{n-j}{n}. c) Show that X_j has a geometric distribution with parameter \frac{n-j}{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 hash-function that maps
a set U to integers 0 ≤ i < p for some prime p. We say that a Hash
function class H is 2-universal 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/p2 for all 2-universal hash function classes. (b) Assume that the universe is a sequence of integers x=(x 1,...,x r) where each xi 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)=(Si. aix i.mod p) with the values ai chosen independently uniformly at random. Show that this class is not 2-universal. (c) Show that the class h(x)=(Si. aix i.+b mod p), where the values ai and b are chosen independently uniformly at random is 2-universal. (d) Consider the following use of 2-universal hash-functions for authentication. Alice and Bob want to send messages over email, and agree on the following authentication scheme. They have in mind a 2-universal set of hash-functions (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 2-universal hash-functions 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 |
|
| 50-51 | Supplementary 50-51 |
|
| -- | 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 19-20 | Section 8.8 exercise 21-22 |
|
|
Chapter 9 in edition V or Chapter 8 in edition IV |
||
| Supplementary 11 | Supplementary 11 | |
-- |
Section 9.4 exercise 21 | |
| -- |
42 | |