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.
- 6.8. A pair of English words is called a rotodrome if one can be circularly shifted (rotated) to create the other word. For example, the words (windup, upwind) are a rotodrome pair, because we can rotate “windup” two positions to the right to get “upwind.”
- Give an efficient algorithm to find all rotodrome pairs among words of length , with a worst-case analysis. Also give a faster expected-time algorithm based on hashing.
- 6.9. Given an array of positive integers, where describes the weight of index , propose an algorithm that randomly picks an index in proportion to its weight.
- 6.10. You are given a function rand7, which generates a uniform random integer in the range 1 to 7. Use it to produce a function rand10, which generates a uniform random integer in the range 1 to 10.
- 6.11. Let be some constant, independent of the input array length . What is the probability that, with a randomly chosen pivot element, the partition subroutine from quicksort produces a split in which the size of both the resulting subproblems is at least times the size of the original array?
- 6.12. Show that for any given load , the error probability of a Bloom filter is minimized when the number of hash functions is .
Back to Chapter List