TAOCP 3.4.2: Random Sampling and Shuffling
Section 3.4.2 exercises: 19/19 solved.
Section 3.4.2. Random Sampling and Shuffling
Exercises from TAOCP Volume 2 Section 3.4.2: 19/19 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M12] | math-simple | verified | 1m46s |
| 2 | [20] | medium | verified | 1m09s |
| 3 | ▶ [22] | medium | verified | 6m36s |
| 4 | [M23] | math-medium | verified | 4m33s |
| 5 | [M24] | math-medium | verified | 2m48s |
| 6 | [M24] | math-medium | solved | 4m31s |
| 7 | [M25] | math-medium | solved | 4m07s |
| 8 | ▶ [M20] | math-medium | verified | 2m55s |
| 9 | [**] | verified | 2m36s | |
| 10 | [**] | verified | 3m18s | |
| 11 | ▶ [**] | verified | 2m19s | |
| 12 | [**] | solved | 4m34s | |
| 13 | [**] | verified | 1m12s | |
| 14 | [**] | verified | 5m11s | |
| 15 | ▶ [30] | hard | verified | 1m32s |
| 16 | [M25] | math-medium | verified | 4m11s |
| 17 | [M22] | math-medium | verified | 2m48s |
| 18 | ▶ [M32] | math-hard | verified | 2m59s |
| 19 | [M28] | math-hard | verified | 3m02s |
TAOCP 3.4.2 Exercise 1
Equation (1) in Section 3.
TAOCP 3.4.2 Exercise 2
Let $N$ be the total number of records in the input file, and let $n$ be the number of records to be selected by Algorithm S.
TAOCP 3.4.2 Exercise 3
There is no contradiction because the two probabilities refer to different events.
TAOCP 3.4.2 Exercise 4
Let $p(m,t)$ denote the probability that exactly $m$ items have been selected from the first $t$ items processed by Algorithm S.
TAOCP 3.4.2 Exercise 5
Let $T$ denote the value of $t$ at termination of Algorithm S, i.
TAOCP 3.4.2 Exercise 6
Let $T$ denote the value of $t$ when Algorithm S terminates.
TAOCP 3.4.2 Exercise 7
Let $S = \{s_1 < s_2 < \dots < s_n\}$ be any fixed $n$-subset of $\{1,2,\dots,N\}$.
TAOCP 3.4.2 Exercise 8
Let - $N$ be the number of records still available, - $n$ be the number of selections still to be made, - $t$ be the number already selected.
TAOCP 3.4.2 Exercise 9
**Exercise 3.
TAOCP 3.4.2 Exercise 10
**Exercise 3.
TAOCP 3.4.2 Exercise 11
Let $M$ be the number of elements that are placed into the reservoir during the first pass of Algorithm R, when a reservoir of size $n$ is used on a file of $N$ records.
TAOCP 3.4.2 Exercise 12
**Exercise 3.
TAOCP 3.4.2 Exercise 13
Let the positions of the cards be numbered modulo $2n-1$.
TAOCP 3.4.2 Exercise 14
Let the original deck be denoted in cyclic order as 2,3,4,5,6,7,8,9,10,J,Q,K,A \; \spadesuit, \dots, A\clubsuit and let $c^+$ denote the successor of card $c$ in this cyclic order (wrapping around fro...
TAOCP 3.4.2 Exercise 15
Algorithm P begins with X_k=k,\qquad 1\le k\le t, and executes steps P2, P4 only until $j=t-n$.
TAOCP 3.4.2 Exercise 16
We are asked to compute a random sample of size $n$ from $\{1,2,\ldots,N\}$, using hashing ideas, $O(n)$ storage, and expected $O(n)$ time.
TAOCP 3.4.2 Exercise 17
Let m=N-n+1.
TAOCP 3.4.2 Exercise 18
We consider $n$ items $(X_1, X_2, \ldots, X_n)$ initially in order $X_j = j$ for $1 \le j \le n$, and a sequence of exchanges X_j \leftrightarrow X_{k_j}, \quad 1 \le j \le n, where $k_1, \dots, k_n$...