Chapter 5 problems
Table of Contents
ch5-problems
5-1
a.
After each INCREMENT operation, the expected value represented by the counter increased by \(\frac{1}{n_{i+1}-n_i}(n_{i+1}-n_i) = 1\), thus after we performed n INCREMENT operations, the expected value represented by the counter is n.
b.
The variance of each INCREMENT operation is
\begin{align*} Var\{X\} &=E[X^2]-E[X]^2\\ &=99 \end{align*}The n INCREMENT operations are independent, thus the total variance is
\begin{align*} Var\{X[n]\} &=\sum_{i=1}^{n}Var\{X_i\}\\ &=99n \end{align*}
5-2
a.
RANDOM-SEARCH(A, x) let S to be an empty set n = A.length while S.length < n i = RANDOM(1, n) if i not in S S.add(i) if A[i] == x return i return NILb.
The problems is a geometric distribution, the expected value of trials is \(n\).
c.
The expected value of trials is \(n/k\).
d.
The expected value of trials is \(n\ln n + O(1)\), the problem is equivalent to the problem of balls and bins which each bin contains at least one ball.
e.
The average running time is \(\Theta((n+1)/2)\), the worst case running time is \(\Theta(n)\).
f.
The average running time is \(\Theta((n+1)/(k+1))\), the worst case running time is \(\Theta(n-k+1)\).
g.
The average running time and the worst case running time are the same \(\Theta(n)\).
h.
Shuffling the input array costs \(\Theta(n)\) running time, the rest is same as DETERMINISTIC-SEARCH, the expected running time is the average running time of DETERMINISTIC-SEARCH.
i.
I would never use the RANDOM-SEARCH, and I prefer SCRAMBLE-SEARCH to DETERMINISTIC-SEARCH when the input array is less random.