1. Suppose you have a bag of 10 coins. Nine of them are fair coins, that is, if you toss any of these 9 coins the probability of getting a head, P(H) = 1/2. Similarly, probability of getting a tail, P(T) = 1/2. The other coin is biased it has head on both sides. Use indicator random variables to compute expected number of heads, if all 10 coins are tossed together.

2. Suppose n customers gives a hat to a hat-check person, and a overcoat to a coat-check person. The hatcheck person gives the hats back to the customers in a random order. The overcoat-check person does the same thing. Use indicator random variables to compute the expected number of customers who get back their own hat and own overcoat? Note you have to compute the number of customers who get both their own hat and own overcoat.

3. Suppose we use RANDOMIZED-SELECTION in Section 9.2 to select the maximum element of the array A= [3, 1, 2, 9, 0, 5, 4, 7, 6, 8]. (a) Describe a sequence of partitions that results in a worst-case performance of RANDOMIZEDSELECTION. (b) Describe a sequence of partitions that results in a best-case performance of RANDOMIZEDSELECTION.

4. Assume a Hash table has 9 slots and the hash function h(k) = k mod 9 is used to hash keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 in the table with collision resolution by chaining. (a) Show the hash table obtained after inserting all 9 keys. (b) Under the assumption of simple uniform hashing, calculate expected number of steps a successful search takes. (c) Under the assumption of simple uniform hashing, calculate expected number of steps an unsuccessful search takes.

5. Assume a Hash table has 11 slots and an ordinary hash function h(k) = k mod 9 is used for first hash. The keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 are inserted in the table with collision resolution using open addressing. (a) Show the hash table obtained after inserting all 9 keys, if linear probing is used. (b) Show the hash table obtained after inserting all 9 keys, if quadratic probing with c1 = 1 and c2 = 3 is used.

This problem set covers contents of sections 5.1, 5.2, 9.2, 11.2 and 114. To solve these problems you will use 2ndicator random variables. 1. Suppose you have a bag of 10 coins. Nine of them are fair coins, that is, if you toss any of these 9 coins the probability of getting a head, P(H) = 1/2. Similarly, probability of getting a tail, P(T) = 1/2 The other coin is biased - it has head on both sides. Use indicator random variables to compute expected number of heads, if all 10 coins are tossed together. 2. Suppose n customers gives a hat to a hat-check person, and a overcoat to a coat-check person. The hat check person gives the hats back to the customers in a random order. The overcoat-check person does the same thing. Use indicator random variables to compute the expected number of customers who get back their own hat and own overcoat? Note you have to compute the number of customers who get both their own hat and own overcoat . 3. Suppose we use RANDOMIZED-SELECTION in Section 9.2 to select the maximum element of the array A = (3, 1, 2, 9, 0, 5, 4, 7, 6, 8 ) (a) Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED SELECTION. (b) Describe a sequence of partitions that results in a best-case performance of RANDOMIZED SELECTION. 4. Assume a Hash table has 9 slots and the hash function h(k) = k mod 9 is used to hash keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 in the table with collision resolution by chaining (a) Show the hash table obtained after inserting all 9 keys. (b) Under the assumption of simple uniform hashing, calculate expected number of steps a successful search takes. (c) Under the assumption of simple uniform hashing, calculate expected number of steps an unsuc- cessful search takes. 5. Assume a Hash table has 11 slots and an ordinary hash function h(k) = k mod 9 is used for first hash. The keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 are inserted in the table with collision resolution using open addressing. (a) Show the hash table obtained after inserting all 9 keys, if linear probing is used. (b) Show the hash table obtained after inserting all 9 keys, if quadratic probing with C =1 and C2 = 3 is used