Chapter 6

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Hashing and Randomized Algorithms


6.1. You are given unbiased coins, and perform the following process to generate all heads. Toss all coins independently at random onto a table. Each round consists of picking up all the tails-up coins and tossing them onto the table again. You repeat until all coins are heads.
(a) What is the expected number of rounds performed by the process?
(b) What is the expected number of coin tosses performed by the process?


6.2. Suppose we flip coins each of known bias, such that is the probability of the th coin being a head. Present an efficient algorithm to determine the exact probability of getting exactly heads given .

6.3. An inversion of a permutation is a pair of elements that are out of order.
(a) Show that a permutation of items has at most inversions. Which permutation(s) have exactly n(n - 1)/2 inversions?
(b) Let P be a permutation and be the reversal of this permutation. Show that and have a total of exactly inversions.
(c) Use the previous result to argue that the expected number of inversions in a random permutation is .


6.4. A derangement is a permutation of such that no item is in its proper position, that is, for all . What is the probability that a random permutation is a derangement?


6.5. An all-Beatles radio station plays nothing but recordings by the Beatles, selecting the next song at random (uniformly with replacement). They get through about ten songs per hour. I listened for 90 minutes before hearing a repeated song. Estimate how many songs the Beatles recorded.


6.6. Given strings and of length and respectively, find the shortest window in that contains all the characters in in expected time.

6.7. Design and implement an efficient data structure to maintain a least recently used (LRU) cache of integer elements. A LRU cache will discard the least recently accessed element once the cache has reached its capacity, supporting the following operations:
get(k)– Return the value associated with the key if it currently exists in the cache, otherwise return -1.
put(k,v) – Set the value associated with key to , or insert if is not already present. If there are already items in the queue, delete the least recently used item before inserting . Both operations should be done in expected time.


Randomized Algorithms






Back to Chapter List