Difference between pages "Chapter List" and "Chapter 6"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "Chapters *Chapter 1 *Chapter 2 *Chapter 3 *Chapter 4 *Chapter 5 *Chapter 6 *Chapter 7 *Chapter 8 *Chapter 9 *Chapter 10 *C...") |
|||
Line 1: | Line 1: | ||
− | + | =Hashing and Randomized Algorithms= | |
− | + | ===Probability=== | |
− | + | :[[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. 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]]. 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. 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=== | |
− | + | :[[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=== | ||
+ | |||
+ | :6.8 | ||
+ | |||
+ | |||
+ | :[[6.9]] | ||
+ | |||
+ | |||
+ | :6.10 | ||
+ | |||
+ | |||
+ | :[[6.11]] | ||
+ | |||
+ | |||
+ | :6.12 | ||
+ | |||
+ | |||
+ | |||
+ | Back to [[Chapter List]] |
Revision as of 17:57, 14 September 2020
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
- 6.10
- 6.12
Back to Chapter List