# Difference between revisions of "Chapter 6"

Jump to navigation
Jump to search

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

## Revision as of 17:53, 14 September 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.6

### Randomized Algorithms

- 6.8

- 6.10

- 6.12

Back to Chapter List