# Chapter 6

Jump to navigation
Jump to search

# Hashing and Randomized Algorithms

### Probability

- 6.1. You are given [math]\displaystyle{ n }[/math] unbiased coins, and perform the following process to generate all heads. Toss all [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ n }[/math] coins each of known bias, such that [math]\displaystyle{ p_i }[/math] is the probability of the [math]\displaystyle{ i }[/math]th coin being a head. Present an efficient algorithm to determine the exact probability of getting exactly [math]\displaystyle{ k }[/math] heads given [math]\displaystyle{ p_1, . . . , p_n \in [0, 1] }[/math].

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

- 6.4. A derangement is a permutation [math]\displaystyle{ p }[/math] of [math]\displaystyle{ {1, . . . , n} }[/math] such that no item is in its proper position, that is, [math]\displaystyle{ p_i \neq i }[/math] for all [math]\displaystyle{ 1 \leq i \leq n }[/math]. What is the probability that a random permutation is a derangement?

### Hashing

- 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 [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] of length [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math] respectively, find the shortest window in [math]\displaystyle{ S }[/math] that contains all the characters in [math]\displaystyle{ T }[/math] in expected [math]\displaystyle{ O(n + m) }[/math] time.

- 6.7. Design and implement an efficient data structure to maintain a
*least recently used*(LRU) cache of [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ k }[/math] if it currently exists in the cache, otherwise return -1. - •
*put(k,v)*– Set the value associated with key [math]\displaystyle{ k }[/math] to [math]\displaystyle{ v }[/math], or insert if [math]\displaystyle{ k }[/math] is not already present. If there are already [math]\displaystyle{ n }[/math] items in the queue, delete the least recently used item before inserting [math]\displaystyle{ (k, v) }[/math]. Both operations should be done in [math]\displaystyle{ O(1) }[/math] expected time.

### Randomized Algorithms

- 6.8. A pair of English words [math]\displaystyle{ (w_1, w_2) }[/math] 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 [math]\displaystyle{ n }[/math] words of length [math]\displaystyle{ k }[/math], with a worst-case analysis. Also give a faster expected-time algorithm based on hashing.

- 6.9. Given an array [math]\displaystyle{ w }[/math] of positive integers, where [math]\displaystyle{ w[i] }[/math] describes the weight of index [math]\displaystyle{ i }[/math], 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 [math]\displaystyle{ 0 \lt \alpha \lt 1/2 }[/math] be some constant, independent of the input array length [math]\displaystyle{ n }[/math]. 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 [math]\displaystyle{ \alpha }[/math] times the size of the original array?

- 6.12. Show that for any given load [math]\displaystyle{ m/n }[/math], the error probability of a Bloom filter is minimized when the number of hash functions is [math]\displaystyle{ k = exp(-1)/(m/n) }[/math].

Back to Chapter List