# Difference between revisions of "Chapter 6"

Jump to navigation
Jump to search

m (Protected "Chapter 6" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite))) |
|||

(3 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

=Hashing and Randomized Algorithms= | =Hashing and Randomized Algorithms= | ||

− | === | + | ===Probability=== |

− | :[[6.1]] | + | :[[6.1]]. You are given <math>n</math> unbiased coins, and perform the following process to generate all heads. Toss all <math>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.1|Solution]] | ||

− | :6.2 | + | :6.2. Suppose we flip <math>n</math> coins each of known bias, such that <math>p_i</math> is the probability of the <math>i</math>th coin being a head. Present an efficient algorithm to determine the exact probability of getting exactly <math>k</math> heads given <math>p_1, . . . , p_n \in [0, 1]</math>. |

− | :[[6.3]] | + | :[[6.3]]. An inversion of a permutation is a pair of elements that are out of order. |

+ | :(a) Show that a permutation of <math>n</math> items has at most <math>n(n - 1)/2</math> inversions. Which permutation(s) have exactly n(n - 1)/2 inversions? | ||

+ | :(b) Let P be a permutation and <math>P^r</math> be the reversal of this permutation. Show that <math>P</math> and <math>P^r</math> have a total of exactly <math>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>n(n - 1)/4</math>. | ||

+ | [[6.3|Solution]] | ||

− | :6.4 | + | :6.4. A derangement is a permutation <math>p</math> of <math>{1, . . . , n}</math> such that no item is in its proper position, that is, <math>p_i \neq i</math> for all <math>1 \leq i \leq n</math>. What is the probability that a random permutation is a derangement? |

− | |||

===Hashing=== | ===Hashing=== | ||

− | :[[6.5]] | + | :[[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.5|Solution]] | |

− | |||

+ | :6.6. Given strings <math>S</math> and <math>T</math> of length <math>n</math> and <math>m</math> respectively, find the shortest window in <math>S</math> that contains all the characters in <math>T</math> in expected <math>O(n + m)</math> time. | ||

− | |||

+ | :[[6.7]]. Design and implement an efficient data structure to maintain a ''least recently used'' (LRU) cache of <math>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>k</math> if it currently exists in the cache, otherwise return -1. | ||

+ | :• ''put(k,v)'' – Set the value associated with key <math>k</math> to <math>v</math>, or insert if <math>k</math> is not already present. If there are already <math>n</math> items in the queue, delete the least recently used item before inserting <math>(k, v)</math>. Both operations should be done in <math>O(1)</math> expected time. | ||

+ | [[6.7|Solution]] | ||

===Randomized Algorithms=== | ===Randomized Algorithms=== | ||

− | :6.8 | + | :6.8. A pair of English words <math>(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>n</math> words of length <math>k</math>, with a worst-case analysis. Also give a faster expected-time algorithm based on hashing. | ||

− | :[[6.9]] | + | :[[6.9]]. Given an array <math>w</math> of positive integers, where <math>w[i]</math> describes the weight of index <math>i</math>, propose an algorithm that randomly picks an index in proportion to its weight. |

+ | [[6.9|Solution]] | ||

− | :6.10 | + | :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]] | + | :[[6.11]]. Let <math>0 < \alpha < 1/2</math> be some constant, independent of the input array length <math>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>\alpha</math> times the size of the original array? |

+ | [[6.11|Solution]] | ||

− | :6.12 | + | :6.12. Show that for any given load <math>m/n</math>, the error probability of a Bloom filter is minimized when the number of hash functions is <math>k = exp(-1)/(m/n)</math>. |

Back to [[Chapter List]] | Back to [[Chapter List]] |

## Latest revision as of 18:08, 1 October 2020

# Hashing and Randomized Algorithms

### Probability

- 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?

### 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 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

- 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