TAOCP 1.2.10: Analysis of an Algorithm
Section 1.2.10 exercises: 22/22 solved.
Section 1.2.10. Analysis of an Algorithm
Exercises from TAOCP Volume 1 Section 1.2.10: 22/22 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 40s |
| 2 | [HM16] | hm-medium | verified | 47s |
| 3 | [M15] | math-simple | verified | 4m35s |
| 4 | [M10] | math-simple | verified | 1m10s |
| 5 | [M13] | math-simple | verified | 35s |
| 6 | [HM27] | hm-hard | verified | 2m03s |
| 7 | [M27] | math-hard | verified | 4m19s |
| 8 | [M20] | math-medium | verified | 4m36s |
| 9 | [M25] | math-medium | verified | 1m30s |
| 10 | [M20] | math-medium | verified | 4m16s |
| 11 | [M15] | math-simple | verified | 4m02s |
| 12 | [HM21] | hm-medium | verified | 9m58s |
| 13 | [HM38] | hm-project | verified | 7m56s |
| 14 | [HM30] | hm-hard | verified | 47s |
| 15 | [HM23] | hm-medium | verified | 1m38s |
| 16 | [M25] | math-medium | verified | 41s |
| 17 | [M27] | math-hard | verified | 1m06s |
| 18 | [M28] | math-hard | verified | 2m32s |
| 19 | [M21] | math-medium | verified | 1m21s |
| 20 | [M22] | math-medium | verified | 59s |
| 21 | [HM21] | hm-medium | verified | 2m25s |
| 22 | [HM22] | hm-medium | verified | 1m09s |
TAOCP 1.2.10 Exercise 1
From (4) with $k=0$ and using $p_{n-1,-1}=0$ from (5), p_{n0}=\frac{1}{n}p_{n-1,-1}+\frac{n-1}{n}p_{n-1,0}=\frac{n-1}{n}p_{n-1,0}.
TAOCP 1.2.10 Exercise 2
We are asked to derive Eq.
TAOCP 1.2.10 Exercise 3
Let $X$ be the number of times step M4 is executed when Algorithm M finds the maximum of $n=1000$ distinct items presented in a uniformly random order.
TAOCP 1.2.10 Exercise 4
From Eq.
TAOCP 1.2.10 Exercise 5
Figure 11 corresponds to the coin-tossing experiment of Eq.
TAOCP 1.2.10 Exercise 6
For a probability generating function G(z)=\sum_{k\ge0}p_k z^k, the third semi-invariant (third cumulant) is
TAOCP 1.2.10 Exercise 7
We are asked to analyze **Algorithm M** under the assumption that the sequence X[1], X[2], \dots, X[n] contains **exactly $m$ distinct values**, which are otherwise randomly arranged subject to that c...
TAOCP 1.2.10 Exercise 8
Let $E$ be the event that all of the values $X[1],X[2],\ldots,X[n]$ are distinct.
TAOCP 1.2.10 Exercise 9
Let $X[1],X[2],\ldots,X[n]$ be chosen independently and uniformly from a set of $M$ distinct elements.
TAOCP 1.2.10 Exercise 10
We are asked to determine the probability distribution of $A$, the number of times step M4 is executed, when each $X[k]$ is selected independently and uniformly from a set of $M$ objects, using the re...
TAOCP 1.2.10 Exercise 11
Let G(z) = \sum_{k \ge 0} p_k z^k be the probability generating function (pgf) of a discrete random variable $X$.
TAOCP 1.2.10 Exercise 12
Let G(z)=\sum_{k\ge0}p_kz^k, \qquad \sum_{k\ge0}p_k=1.
TAOCP 1.2.10 Exercise 13
Let G_n(z)=\frac1{n!
TAOCP 1.2.10 Exercise 14
Let G_n(z)=(q+pz)^n,\qquad q=1-p.
TAOCP 1.2.10 Exercise 15
The Poisson distribution with parameter $\mu$ assigns probabilities p_k = e^{-\mu}\frac{\mu^k}{k!
TAOCP 1.2.10 Exercise 16
Let $g_i(z)=\sum_k p_{ik}z^k$ be the probability generating function of a random variable $X_i$, with g_i(1)=1,\qquad \mu_i=g_i'(1),\qquad \sigma_i^2=g_i''(1)+g_i'(1)-g_i'(1)^2.
TAOCP 1.2.10 Exercise 17
Let f(z)=\sum_{k\ge 0} a_k z^k, \qquad g(z)=\sum_{n\ge 0} b_n z^n be generating functions of probability distributions, so $a_k \ge 0$, $b_n \ge 0$, and
TAOCP 1.2.10 Exercise 18
The critical issue in the proposed solution is the hidden assumption that “first element of a reduced problem” corresponds to the first element of the original permutation.
TAOCP 1.2.10 Exercise 19
Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$, and let $b_1 b_2 \ldots b_n$ be its inverse permutation, so that a_k = l \quad \text{if and only if} \quad b_l = k.
TAOCP 1.2.10 Exercise 20
Let M=\max_{1\le k\le n}|a_k-b_k|.
TAOCP 1.2.10 Exercise 21
Let $X\sim \mathrm{Bin}(n,p)$, $q=1-p$, and let $0\le \epsilon \le q$.
TAOCP 1.2.10 Exercise 22
Let $X$ be a sum of independent Bernoulli random variables $X_1,X_2,\ldots,X_n$, where $X_k$ takes the value $1$ with probability $p_k$ and $0$ with probability $q_k=1-p_k$.