Chapter 7 problems
ch7-problems
7-1
a.
A = (13 19 9 5 12 8 7 4 11 2 6 21), x = 13, p = 1, r = 12, i = 0, j = 13 -> A = (6 19 9 5 12 8 7 4 11 2 13 21), i = 1, j = 11 -> A = (6 13 9 5 12 8 7 4 11 2 19 21), i = 2, j = 11 -> A = (6 2 9 5 12 8 7 4 11 13 19 21), i = 2, j = 10 -> A = (6 2 9 5 12 8 7 4 11 13 19 21), return 10
b.
We start with \(i = p - 1\) and \(j = r + 1\), then we keep increasing i and decreasing j until \(i \geq j\), thus we never access an element of A outside the subarray A[p..r].
c.
We terminated when \(i \geq j\), and we know that at least one exchange happens, thus the procedure returns a value j such that \(p \leq j < r\).
d.
When the procedure terminates, we have \(A[p..j] \leq x \leq A[j+1..r]\).
e.
HOARE-QUICKSORT(A, p, r) if p < r q = HOARE-PARTITION(A, p, r) HOARE-QUICKSORT(A, p, q) HOARE-QUICKSORT(A, q + 1, r)
7-2
a.
The running time is \(T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)\).
b.
PARTITION'(A, p, r) x = A[r] i = j = p - 1 for k = p to r - 1 if A[k] < x i = i + 1 j = j + 1 y = A[j] A[j] = A[i] A[i] = A[k] A[k] = y else if A[k] == x: j = j + 1 exchange A[j] with A[k] exchange A[r] with A[j + 1] return i + 1, j + 1c.
RANDOMIZED-PARTITION'(A, p, r) i = RANDOM(p, r) exchange A[r] with A[i] return PARTITION'(A, p, r)QUICKSORT'(A, p, r) if p < r q, t = RANDOMIZED-PARTITION'(A, p, r) QUICKSORT'(A, p, q - 1) QUICKSORT'(A, t + 1, r)d.
The running time is
\begin{align*} T(n) &=T(m)+T(n-k-m)+O(n) &\text{, m elements less than the pivot, k elements equal to the pivot}\\ &\leq T(m+k)+T(n-m-k)+O(n)\\ &=O(n\lg n) \end{align*}
7-3
a.
We randomly pick the pivot from the n elements, thus the probability that any particular element is chosen as the pivot is \(1 / n\).
Let \(X_i = I\{ith\ smallest\ element\ is\ chosen\ as\ the\ pivot\}\), then
\begin{align*} E[X_i] &=\Pr\text{{we choose the smallest ith element as the pivot}}\\ &=\frac{1}{n} \end{align*}b.
We have
\begin{align*} E[T(n)] &=E\Bigg[\sum_{q=1}^{n}X_q T(\text{when $X_q$ happens})\Bigg]\\ &=E\Bigg[\sum_{q=1}^{n}X_q(T(q-1)+T(n-q)+\Theta(n))\Bigg] \end{align*}c.
We have
\begin{align*} E[T(n)] &=E\Bigg[\sum_{q=1}^{n}X_q(T(q-1)+T(n-q)+\Theta(n))\Bigg]\\ &=E\Bigg[\frac{1}{n}\sum_{q=1}^{n}(T(q-1)+T(n-q)+\Theta(n))\Bigg]\\ &=\frac{2}{n}\sum_{q=2}^{n-1}E[T(q)]+\Theta(n) \end{align*}d.
We have
\begin{align*} \sum_{k=2}^{n-1}k\lg k &\leq \sum_{k=2}^{\lceil n/2 \rceil-1}k\lg(n/2) + \sum_{k=\lceil n/2 \rceil}^{n-1}k\lg n\\ &\leq \frac{n^2}{8}(\lg n-1)+\frac{3n^2}{8}\lg n\\ &=\frac{1}{2}n^2\lg n-\frac{1}{8}n^2 \end{align*}e.
Guess \(E[T(n)] \leq an\lg n\), then
\begin{align*} E[T(n)] &=\frac{2}{n}\sum_{q=2}^{n-1}E[T(q)]+\Theta(n)\\ &\leq \frac{2}{n}\sum_{q=2}^{n-1}aq\lg q+\Theta(n)\\ &\leq \frac{2a}{n}(\frac{1}{2}n^2\lg n-\frac{1}{8}n^2)+\Theta(n) &\text{, From equation (7.7)}\\ &=an\lg n-\frac{a}{4}n+\Theta(n)\\ &\leq an\lg n &\text{, for enough large constant $a$} \end{align*}
7-4
a.
We use loop invariant to prove the correctness of the procedure.
Loop Invariant: At the start of each iteration of the while loop, we have partitioned \(A[1..A.length]\) by \(p\) and sorted \(A[1..p]\).
Initialization: \(A[1..p]\) is empty.
Maintenance: We partition \(A[p..r]\) at \(q\) and sort \(A[p..q-1]\), then we know that \(A[1..q]\) is sorted, and we let \(p = q+1\) and continue with the next iteration.
Termination: The loop terminates when \(p \geq A.length\), thus the array \(A\) is sorted.
b.
When each PARTITION in the recursion does a \([p..r-1]\) to \([r..r]\) split, the stack depth is \(\Theta(n)\).
c.
After each PARTITION, we choose the smaller part for the recursion.
TAIL-RECURSIVE-QUICKSORT(A, p, r) while p < r //Partition and sort the smaller subarray q = PARTITION(A, p, r) if q < (p + r) / 2 TAIL-RECURSIVE-QUICKSORT(A, p, q - 1) p = q + 1 else TAIL-RECURSIVE-QUICKSORT(A, q + 1, r) r = q - 1
7-5
a.
The probability is
\begin{align*} p_i &=\Pr\{x=A'[i]\}\\ &=\frac{(i-1)(n-i)}{\binom{n}{3}} \end{align*}b.
Let \(m = \lfloor (n + 1) / 2 \rfloor\), then the probability of the developed implementation is \(\frac{(m-1)(n-m)}{\binom{n}{3}}\), and the probability of the ordinary implementation is \(\frac{1}{n}\).
The limit ratio of them is
\begin{align*} r &=\lim_{n\to \infty}\frac{\frac{(m-1)(n-m)}{\binom{n}{3}}}{\frac{1}{n}}\\ &=\frac{3}{2} \end{align*}c.
The probability of the ordinary implementation is
\begin{align*} p' &\approx \int_{\frac{n}{3}}^{\frac{2n}{3}} \frac{1}{n}dx\\ &=\frac{1}{3} \end{align*}The probability of the developed implementation is
\begin{align*} p &\approx \int_{\frac{n}{3}}^{\frac{2n}{3}} \frac{(x-1)(n-x)}{\binom{n}{3}}dx\\ \end{align*}And the limit ratio of them is
\begin{align*} r &=\lim_{n\to \infty}\frac{p}{p'}\\ &=\frac{13}{9} \end{align*}d.
The median-of-3 method only improves the probability of choosing a good pivot, the running time is still \(\Omega(n \lg n)\).
7-6
a.
The FUZZY-SORT should take advantage of overlapping intervals by consider the elements with overlapped intervals as equal, then use the developed algorithm in problem 7-2.
FUZZY-SORT(A, B, p, r) if p < r q, s = FUZZY-PARTITION(A, B, p, r) FUZZY-SORT(A, B, p, q - 1) FUZZY-SORT(A, B, s + 1, r)FUZZY-PARTITION(A, B, p, r) i = j = p - 1 left = A[r] right = B[r] for k = p to r - 1 if B[k] < left x = A[k] y = B[k] i = i + 1 j = j + 1 A[k], B[k] = A[j], B[j] A[j], B[j] = A[i], B[i] A[i], B[i] = x, y else if A[k] <= right if A[k] > left left = A[k] if B[k] < right right = B[k] j = j + 1 exchange A[k], B[k] with A[j], B[j] exchange A[r], B[r] with A[j + 1], B[j + 1] return i + 1, j + 1b.
Assume the partition on n elements returns k overlapped elements, then we get the running time
\begin{align*} T(n) = T(n-k-i) + T(i) + \Theta(n) \end{align*}The expected running time is \(\Theta(n\lg n)\) when k is negligible to n.
When all the intervals overlap, the running time is \(\Theta(n)\).