Chapter 2 problems
Table of Contents
ch2-problems
2-1
a.
The worst-case running time is
\begin{align*} T(n,k)&=n/k\times\Theta(k^2)\\ &=\Theta(nk) \end{align*}b.
MERGE-SUBLISTS(S) let S'[1..S.length // 2] to be new array for i = 1 to S.length // 2 S'[i] = MERGE(S[2 * i - 1], S[2 * i]) if S.length % 2 != 0 S'.append(S[S.length]) return MERGE-SUBLIST(S')c.
\(k = \Theta(\lg{n})\)
d.
In practice, k should be the largest value that insertion sort is faster than merge sort.
2-2
a.
We need to prove A' is a permutation of A.
b.
Loop Invariant: A[j] is the smallest value of A[j..n], and A[j..n] is a permutation of the original A[j..n].
Initialization: A[j..n] is empty.
Maintenance: After each iteration, A[j - 1] becomes the smallest value of A[j - 1..n], and A[j - 1..n] is a permutation of the original A[j - 1..n].
Termination: A[i] is the smallest value of A[i..n], and A[i..n] is a permutation of the original A[i..n].
c.
Loop Invariant: At the start of each iteration of the outer loop, the subarray A[1..i - 1] is sorted and contains the smallest (i - 1) elements. And A remains to be a permutation of the original A.
Initialization: At the start of first iteration, the subarray A[1..i - 1] is empty, and A is the original A.
Maintenance: At the end of each iteration, the element A[i] is the smallest of A[i..n], and we are using exchange to move the elements, so A is a permutation of the original A.
Termination: The iteration terminates when i = n - 1, this means A[1..n - 1] is sorted and contains the smallest (n - 1) elements, and A is a permutation of the original A, so A[n] is the largest element of A, A is correctly sorted.
d.
The running time of bubblesort is
\begin{align*} T(n)&=\sum_{i=1}^{n-1}(n-i)\Theta(1)\\ &=\frac{n(n-1)}{2}\Theta(1)\\ &=\Theta(n^2) \end{align*}Bubblesort in any cases has the same running time as the insertion sort in worst case.
2-3
a.
\(\Theta(n)\)
b.
NAIVE-POLYNOMIAL-EVALUATION(A, x) y = 0 for i = 1 to A.length y = y + A[i] * POWER(x, i - 1) return yThe running time is \(\Theta(n^2)\), if POWER has \(\Theta(n)\) running time.
c.
Initialization: i = n, and y = 0
Maintenance: After the ith iteration,
\begin{align*} y&=a_i+x\sum_{k=0}^{n-(i+1)}a_{k+i+1}x^k\\ &=a_ix^0+\sum_{k=1}^{n-i}a_{k+i}x^k\\ &=\sum_{k=0}^{n-i}a_{k+i}x^k \end{align*}Termination: The loop terminates when i = -1,
\begin{align*} y&=\sum_{k=0}^{n-(-1+1)}a_{k-1+1}x^k\\ &=\sum_{k=0}^{n}a_kx^k \end{align*}- d. The loop invariant shows that the given code fragment correctly evaluates the polynomial.
2-4
a.
(1, 5), (2, 5), (3, 4), (3, 5), (4, 5)
b.
The array in non-increase order [n, n - 1, …, 2, 1] has the most inversions. The number of inversions is \(\binom{n}{2} = \frac{n(n-1)}{2}\).
c.
The running time is in proportion to the number of inversions in the input array.
Consider the (i - 1)th iteration of the outer loop in the insertion sort, the subarray A[1..i - 1] is a sorted permutation of the original A[1..i - 1]. Each iteration of the inner loop reduces the number of inversions by a pair (A[j], A[i]). The total number of iterations of the inner loop is in conclusion the same as the number of inversions.
d.
MERGE-SORT(A, p, r) inv = 0 if p < r q = (p + r) // 2 inv = inv + MERGE-SORT(A, p, q) inv = inv + MERGE-SORT(A, q + 1, r) inv = inv + MERGE(A, p, q, r) return invMERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1 + 1] and R[1..n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = \infty R[n2 + 1] = \infty i = 1 j = 1 inv = 0 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] inv = inv + n1 + 1 - i j = j + 1 return inv