P1 (15 points) Alice and Bob play the following game by tossing a fair (unbiased) coin. Each player takes turns starting with Alice’s turn.
• If Alice turns up heads she wins at once, or else Bob gets a turn.
• If Bob turns up tails, he wins at once, or else Alice gets a turn.
The game goes on indefinitely until one player wins.
(A, 5 points) What is the probability that Alice wins? What is the expected number of tosses in the game?
(B, 10 points) Design a game between Alice and Bob where the probability that Bob wins is precisely . Each round of game must have the following format:
1. Alice tosses the coin n times. If we see k < n heads then she wins else Bob gets a turn.
2. Bob tosses the coin l times. If we see m < l tails he wins else Alice gets a turn.
The game can go for ever or can end after finitely many moves with one of the players declared the winner if the game reaches that turn. Here is an example:
1. Alice tosses 3 coins. If she sees 2 tails then she wins else Bob gets a turn.
2. Bob tosses 2 coins. If he gets at least one head, he wins or else Alice gets a turn.
3. Alice wins.
P2 (15 points) Consider the keys {1,...,n} inserted in a random order into a binary search tree. We showed in class that a node i is the ancestor of a node j if and only if i is the first key that was chosen amongst all nodes {i,...,j} (or {j,...,i} if j < i). The probability of this happening was found to be . Answer the following questions about leaves of the tree.
(A, 10 points) What is the probability that node k is a leaf? Hint: Your answer should analyze nodes 1,n separately from nodes 2,...,n − 1.
(B, 5 points ) Calculate the expected number of leaf nodes. Your answer should be exact: asymptotic notations or bounds are not acceptable.
P3 (20 points) Suppose we are interested in hashing n bit keys into m bit hash values to hash into a table of size 2m. We view our key as a bit vector of n bits in binary.
1
Eg., for n = 4, the key 14 = 1 .
1
0
1
The hash family is defined by random Boolean matrices H with m rows and n columns. To compute the hash function, we perform a matrix multiplication. Eg., with m = 3 and n = 4, we can have a matrix H such as
.
The value of the hash function H(14) is now obtained by multiplying
The matrix multiplication is carried out using AND for multiplication and XOR instead of addition.
2
