admin 管理员组文章数量: 1184232
1.1-1
Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.
- Sorting: browse the price of the restaurants with ascending prices on NTU street.
- Convex hull: computing the diameter of set of points.
1.1-2
Other than speed, what other measures of efficiency might one use in a real-world setting?
Memory efficiency and coding efficiency.
1.1-3
Select a data structure that you have seen previously, and discuss its strengths and limitations.
Linked-list:
- Strengths: insertion and deletion.
- Limitations: random access.
1.1-4
How are the shortest-path and traveling-salesman problems given above similar? How are they different?
- Similar: finding path with shortest distance.
- Different: traveling-salesman has more constrains.
1.1-5
Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is ‘‘approximately’’ the best is good enough.
- Best: find the GCD of two positive integer numbers.
- Approximately: find the solution of differential equations.
1.2-1
Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.
Drive navigation.
1.2-2
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size nnn , insertion sort runs in 8n28n^28n2 steps, while merge sort runs in 64nlgn64n\lg n64nlgn steps. For which values of nnn does insertion sort beat merge sort?
\begin{align}
8n^2 & < 64n\lg n \\
2^n & < n^8 \\
n & \le 43.
\end{align}
1.2-3
What is the smallest value of nnn such that an algorithm whose running time is 100n2100n^2100n2 runs faster than an algorithm whose running time is 2n2^n2n on the same machine?
\begin{align}
100n^2 & < 2^n \\
n & \ge 15.
\end{align}
For each function f(n)f(n)f(n) and time ttt in the following table, determine the largest size nnn of a problem that can be solved in time ttt, assuming that the algorithm to solve the problem takes f(n)f(n)f(n) microseconds.
For each function f(n)f(n)f(n) and time ttt in the following table, determine the largest size nnn of a problem that can be solved in time ttt, assuming that the algorithm to solve the problem takes f(n)f(n)f(n) microseconds.
2-1
Although merge sort runs in Θ(nlgn)\Theta(n\lg n)Θ(nlgn) worst-case time and insertion sort runs in Θ(n2)\Theta(n^2)Θ(n2) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/kn / kn/k sublists of length kkk are sorted using insertion sort and then merged using the standard merging mechanism, where kkk is a value to be determined.
a. Show that insertion sort can sort the n/kn / kn/k sublists, each of length kkk, in Θ(nk)\Theta(nk)Θ(nk) worst-case time.
b. Show how to merge the sublists in Θ(nlg(n/k))\Theta(n\lg(n / k))Θ(nlg(n/k)) worst-case time.
c. Given that the modified algorithm runs in Θ(nk+nlg(n/k))\Theta(nk + n\lg(n / k))Θ(nk+nlg(n/k)) worst-case time, what is the largest value of kkk as a function of nnn for which the modified algorithm has the same running time as standard merge sort, in terms of Θ\ThetaΘ-notation?
d. How should we chosse kkk in practice?
a. Insertion sort takes Θ(k2)\Theta(k^2)Θ(k2) time per kkk-element list in the worst case. Therefore, sorting n/kn / kn/k lists of kkk elements each takes Θ(k2n/k)=Θ(nk)\Theta(k^2n / k) = \Theta(nk)Θ(k2n/k)=Θ(nk) worst-case time.
b. Just extending the 222-list merge to merge all the lists at once would take Θ(n⋅(n/k))=Θ(n2/k)\Theta(n \cdot(n / k)) = \Theta(n^2/k)Θ(n⋅(n/k))=Θ(n2/k) time (nnn from copying each element once into the result list, n/kn / kn/k from examining n/kn / kn/k lists at each step to select next item for result list).
To achieve Θ(nlg(n/k))\Theta(n\lg(n / k))Θ(nlg(n/k))-time merging, we merge the lists pairwise, then merge the resulting lists pairwise, and so on, until there’s just one list. The pairwise merging requires Θ(n)\Theta(n)Θ(n) work at each level, since we are still working on nnn elements, even if they are partitioned among sublists. The number of levels, starting with n/kn / kn/k lists (with kkk elements each) and finishing with 1 list (with nnn elements), is ⌈lg(n/k)⌉\lceil \lg(n / k) \rceil⌈lg(n/k)⌉. Therefore, the total running time for the merging is Θ(nlg(n/k))\Theta(n\lg(n / k))Θ(nlg(n/k)).
c. The modified algorithm has the same asymptotic running time as standard merge sort when Θ(nk+nlg(n/k))=Θ(nlgn)\Theta(nk + n\lg(n / k)) = \Theta(n\lg n)Θ(nk+nlg(n/k))=Θ(nlgn). The largest asymptotic value of kkk as a function of nnn that satisfies this condition is k=Θ(lgn)k = \Theta(\lg n)k=Θ(lgn).
To see why, first observe that kkk cannot be more than Θ(lgn)\Theta(\lg n)Θ(lgn) (i.e., it can’t have a higher-order term than lgn\lg nlgn), for otherwise the left-hand expression wouldn’t be Θ(nlgn)\Theta(n\lg n)Θ(nlgn) (because it would have a higher-order term than nlgnn\lg nnlgn). So all we need to do is verify that k=Θ(lgn)k = \Theta(\lg n)k=Θ(lgn) works, which we can do by plugging k=lgnk = \lg nk=lgn into
Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)\Theta(nk + n\lg(n / k)) = \Theta(nk + n\lg n - n\lg k)Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)
to get
Θ(nlgn+nlgn−nlglgn)=Θ(2nlgn−nlglgn),\Theta(n\lg n + n\lg n - n\lg\lg n) = \Theta(2n\lg n - n\lg\lg n),Θ(nlgn+nlgn−nlglgn)=Θ(2nlgn−nlglgn),
which by taking just the high-order term and ignorin the constant coefficient, equals Θ(nlgn)\Theta(n\lg n)Θ(nlgn).
d. In practice, kkk should be the largest list length on which insertion sort is faster than merge sort.
2-2
Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.
BUBBLESORT(A) for i = 1 to A.length - 1 for j = A.length downto i + 1 if A[j] < A[j - 1] exchange A[j] with A[j - 1]a. Let A′A'A′ denote the output of BUBBLESORT(A)\text{BUBBLESORT}(A)BUBBLESORT(A) To prove that BUBBLESORT\text{BUBBLESORT}BUBBLESORT is correct, we need to prove that it terminates and that
(2.3)A′[1]≤A′[2]≤⋯≤A′[n],A'[1] \le A'[2] \le \cdots \le A'[n], \tag{2.3}A′[1]≤A′[2]≤⋯≤A′[n],(2.3)
where n=A.lengthn = A.lengthn=A.length. In order to show that BUBBLESORT actually sorts, what else do we need to prove?
The next two parts will prove inequality (2.3)\text{(2.3)}(2.3).
b. State precisely a loop invariant for the for loop in lines 2–4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.
c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1–4 that will allow you to prove inequality (2.3)\text{(2.3)}(2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.
d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?
a. We need to show that the elements of A′A'A′ form a permutation of the elements of AAA.
b. Loop invariant: At the start of each iteration of the for loop of lines 2–4, A[j]=minA[k]:j≤k≤nA[j] = \min\\{A[k]: j \le k \le n\\}A[j]=minA[k]:j≤k≤n and the subarray A[j..n]A[j..n]A[j..n] is a permutation of the values that were in A[j..n]A[j..n]A[j..n] at the time that the loop started.
Initialization: Initially, j=nj = nj=n, and the subarray A[j..n]A[j..n]A[j..n] consists of single element A[n]A[n]A[n]. The loop invariant trivially holds.
Maintenance: Consider an iteration for a given value of jjj. By the loop invariant, A[j]A[j]A[j] is the smallest value in A[j..n]A[j..n]A[j..n]. Lines 3–4 exchange A[j]A[j]A[j] and A[j−1]A[j - 1]A[j−1] if A[j]A[j]A[j] is less than A[j−1]A[j - 1]A[j−1], and so A[j−1]A[j - 1]A[j−1] will be the smallest value in A[j−1..n]A[j - 1..n]A[j−1..n] afterward. Since the only change to the subarray A[j−1..n]A[j - 1..n]A[j−1..n] is this possible exchange, and the subarray A[j..n]A[j..n]A[j..n] is a permutation of the values that were in A[j..n]A[j..n]A[j..n] at the time that the loop started, we see that A[j−1..n]A[j - 1..n]A[j−1..n] is a permutation of the values that were in A[j−1..n]A[j - 1..n]A[j−1..n] at the time that the loop started. Decrementing jjj for the next iteration maintains the invariant.
Termination: The loop terminates when jjj reaches iii. By the statement of the loop invariant, A[i]=minA[k]:i≤k≤nA[i] = \min\\{A[k]: i \le k \le n\\}A[i]=minA[k]:i≤k≤n and A[i..n]A[i..n]A[i..n] is a permutation of the values that were in A[i..n]A[i..n]A[i..n] at the time that the loop started.
c. Loop invariant: At the start of each iteration of the for loop of lines 1–4, the subarray A[1..i−1]A[1..i - 1]A[1..i−1] consists of the i−1i - 1i−1 smallest values originally in A[1..n]A[1..n]A[1..n], in sorted order, and A[i..n]A[i..n]A[i..n] consists of the n−i+1n - i + 1n−i+1 remaining values originally in A[1..n]A[1..n]A[1..n].
Initialization: Before the first iteration of the loop, i=1i = 1i=1. The subarray A[1..i−1]A[1..i - 1]A[1..i−1] is empty, and so the loop invariant vacuously holds.
Maintenance: Consider an iteration for a given value of iii. By the loop invariant, A[1..i−1]A[1..i - 1]A[1..i−1] consists of the iii smallest values in A[1..n]A[1..n]A[1..n], in sorted order. Part (b) showed that after executing the for loop of lines 2–4, A[i]A[i]A[i] is the smallest value in A[i..n]A[i..n]A[i..n], and so A[1..i]A[1..i]A[1..i] is now the iii smallest values originally in A[1..n]A[1..n]A[1..n], in sorted order. Moreover, since the for loop of lines 2–4 permutes A[i..n]A[i..n]A[i..n], the subarray A[i+1..n]A[i + 1..n]A[i+1..n] consists of the n−in - in−i remaining values originally in A[1..n]A[1..n]A[1..n].
Termination: The for loop of lines 1–4 terminates when i=ni = ni=n, so that i−1=n−1i - 1 = n - 1i−1=n−1. By the statement of the loop invariant, A[1..i−1]A[1..i - 1]A[1..i−1] is the subarray A[1..n−1]A[1..n - 1]A[1..n−1], and it consists of the n−1n - 1n−1 smallest values originally in A[1..n]A[1..n]A[1..n], in sorted order. The remaining element must be the largest value in A[1..n]A[1..n]A[1..n], and it is in A[n]A[n]A[n]. Therefore, the entire array A[1..n]A[1..n]A[1..n] is sorted.
Note: Tn the second edition, the for loop of lines 1–4 had an upper bound of A.lengthA.lengthA.length. The last iteration of the outer for loop would then result in no iterations of the inner for loop of lines 1–4, but the termination argument would simplify: A[1..i−1]A[1..i - 1]A[1..i−1] would be the entire array A[1..n]A[1..n]A[1..n], which, by the loop invariant, is sorted.
d. The running time depends on the number of iterations of the for loop of lines 2–4. For a given value of iii, this loop makes n−in - in−i iterations, and iii takes on the values 1,2,…,n−11, 2, \ldots, n - 11,2,…,n−1. The total number of iterations, therefore, is
\begin{align}
\sum_{i = 1}^{n - 1} (n - i)
& = \sum_{i = 1}^{n - 1} n - \sum_{i = 1}^{n - 1} i \\
& = n(n - 1) - \frac{n(n - 1)}{2} \\
& = \frac{n(n - 1)}{2} \\
& = \frac{n^2}{2} - \frac{n}{2}.
\end{align}
Thus, the running time of bubblesort is Θ(n2)\Theta(n^2)Θ(n2) in all cases. The worst-case running time is the same as that of insertion sort.
2-3
The following code fragment implements Horner’s rule for evaluating a polynomial
\begin{align}
P(x) & = \sum_{k = 0}^n a_k x^k \\
& = a_0 + x(a_1 + x (a_2 + \cdots + x(a_{n - 1} + x a_n) \cdots)),
\end{align}given the coefficients a0,a1,…,ana_0, a_1, \ldots, a_na0,a1,…,an and a value of xxx:
y = 0 for i = n downto 0 y = a[i] + x * y
a. In terms of Θ\ThetaΘ-notation, what is the running time of this code fragment for Horner’s rule?
b. Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule
c. Consider the following loop invariant: At the start of each iteration of the for loop of lines 2-3,
y=∑k=0n−(i+1)ak+i+1xk.y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k.y=k=0∑n−(i+1)ak+i+1xk.
Interpret a summation with no terms as equaling 000. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, y=∑k=0nakxky = \sum_{k = 0}^n a_k x^ky=∑k=0nakxk.
d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0,a1,…,ana_0, a_1, \ldots, a_na0,a1,…,an.
a. Θ(n)\Theta(n)Θ(n).
b.
NAIVE-HORNER()
y = 0
for k = 0 to n
temp = 1
for i = 1 to k
temp = temp * x
y = y + a[i] * m
The running time is Θ(n2)\Theta(n^2)Θ(n2), because of the nested loop. It is obviously slower.
c. Initialization: It is pretty trivial, since the summation has no terms which implies y=0y = 0y=0.
Maintenance: By using the loop invariant, in the end of the iii-the iteration, we have
\begin{align}
y & = a_i + x \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k \\
& = a_i x^0 + \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^{k + 1} \\
& = a_i x^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 at i=−1i = -1i=−1. If we substitute,
y=∑k=0n−i−1ak+i+1xk=∑k=0nakxk.y = \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^k = \sum_{k = 0}^n a_k x^k.y=k=0∑n−i−1ak+i+1xk=k=0∑nakxk.
d. The invariant of the loop is a sum that equals a polynomial with the given coefficients.
2-4
Let A[1..n]A[1..n]A[1..n] be an array of nnn distinct numbers. If i<ji < ji<j and A[i]>A[j]A[i] > A[j]A[i]>A[j], then the pair (i,j)(i, j)(i,j) is called an inversion of AAA.
a. List the five inversions in the array ⟨2,3,8,6,1⟩\langle 2, 3, 8, 6, 1 \rangle⟨2,3,8,6,1⟩.
b. What array with elements from the set 1,2,…,n\\{1, 2, \ldots, n\\}1,2,…,n has the most inversions? How many does it have?
c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
d. Give an algorithm that determines the number of inversions in any permutation of nnn elements in Θ(nlgn)\Theta(n\lg n)Θ(nlgn) worst-case time. (Hint:\textit{Hint:}Hint: Modify merge sort).
a. The inversions are (1,5)(1,5)(1,5), (2,5)(2,5)(2,5), (3,4)(3,4)(3,4), (3,5)(3,5)(3,5), (4,5)(4,5)(4,5). (Remember that inversions are specified by indices rather than by the values in the array.)
b. The array with elements from 1,2,…,n\\{1, 2, \ldots, n\\}1,2,…,n with the most inversions is ⟨n,n−1,n−2,…,2,1⟩\langle n, n - 1, n - 2, \ldots, 2, 1 \rangle⟨n,n−1,n−2,…,2,1⟩. For all 1≤i<j≤n1 \le i < j \le n1≤i<j≤n, there is an inversion (i,j)(i, j)(i,j). The number of such inversions is (n2)=n(n−1)/2\binom{n}{2} = n(n - 1) / 2(2n)=n(n−1)/2.
c. Suppose that the array AAA starts out with an inversion (k,j)(k, j)(k,j). Then k<jk < jk<j and A[k]>A[j]A[k] > A[j]A[k]>A[j]. At the time that the outer for loop of lines 1–8 sets key=A[j]key = A[j]key=A[j], the value that started in A[k]A[k]A[k] is still somewhere to the left of A[j]A[j]A[j]. That is, it’s in A[i]A[i]A[i], where 1≤i<j1 \le i < j1≤i<j, and so the inversion has become (i,j)(i, j)(i,j). Some iteration of the while loop of lines 5–7 moves A[i]A[i]A[i] one position to the right. Line 8 will eventually drop keykeykey to the left of this element, thus eliminating the inversion. Because line 5 moves only elements that are greater than keykeykey, it moves only elements that correspond to inversions. In other words, each iteration of the while loop of lines 5–7 corresponds to the elimination of one inversion.
d. We follow the hint and modify merge sort to count the number of inversions in Θ(nlgn)\Theta(n\lg n)Θ(nlgn) time.
To start, let us define a merge-inversion as a situation within the execution of merge sort in which the MERGE\text{MERGE}MERGE procedure, after copying A[p..q]A[p..q]A[p..q] to LLL and A[q+1..r]A[q + 1..r]A[q+1..r] to RRR, has values xxx in LLL and yyy in RRR such that x>yx > yx>y. Consider an inversion (i,j)(i, j)(i,j), and let x=A[i]x = A[i]x=A[i] and y=A[j]y = A[j]y=A[j] , so that i<ji < ji<j and x>yx > yx>y. We claim that if we were to run merge sort, there would be exactly one mergeinversion involving xxx and yyy. To see why, observe that the only way in which array elements change their positions is within the MERGE\text{MERGE}MERGE procedure. Moreover, since MERGE\text{MERGE}MERGE keeps elements within LLL in the same relative order to each other, and correspondingly for RRR, the only way in which two elements can change their ordering relative to each other is for the greater one to appear in LLL and the lesser one to appear in RRR. Thus, there is at least one merge-inversion involving xxx and yyy. To see that there is exactly one such merge-inversion, observe that after any call of MERGE\text{MERGE}MERGE that involves both xxx and yyy, they are in the same sorted subarray and will therefore both appear in LLL or both appear in RRR in any given call thereafter. Thus, we have proven the claim.
We have shown that every inversion implies one merge-inversion. In fact, the correspondence between inversions and merge-inversions is one-to-one. Suppose we have a merge-inversion involving values xxx and yyy, where xxx originally was A[i]A[i]A[i] and yyy was originally A[j]A[j]A[j]. Since we have a merge-inversion, x>yx > yx>y. And since xxx is in LLL and yyy is in RRR, xxx must be within a subarray preceding the subarray containing yyy. Therefore xxx started out in a position iii preceding yyy's original position jjj, and so (i,j)(i, j)(i,j) is an inversion.
Having shown a one-to-one correspondence between inversions and mergeinversions, it suffices for us to count merge-inversions.
Consider a merge-inversion involving yyy in RRR. Let zzz be the smallest value in LLL that is greater than yyy. At some point during the merging process, zzz and yyy will be the “exposed” values in LLL and RRR, i.e., we will have z=L[i]z = L[i]z=L[i] and y=R[j]y = R[j]y=R[j] in line 13 of MERGE\text{MERGE}MERGE. At that time, there will be merge-inversions involving yyy and L[i],L[i+1],L[i+2],…,L[n1]L[i], L[i + 1], L[i + 2], \ldots, L[n_1]L[i],L[i+1],L[i+2],…,L[n1], and these n1−i+1n_1 - i + 1n1−i+1 merge-inversions will be the only ones involving yyy. Therefore, we need to detect the first time that zzz and yyy become exposed during the MERGE\text{MERGE}MERGE procedure and add the value of n1−i+1n_1 - i + 1n1−i+1 at that time to our total count of merge-inversions.
The following pseudocode, modeled on merge sort, works as we have just described. It also sorts the array AAA.
COUNT-INVERSIONS(A, p, r)
inversions = 0
if p < r
q = floor((p + r) / 2)
inversions = inversions + COUNT-INVERSIONS(A, p, q)
inversions = inversions + COUNT-INVERSIONS(A, q + 1, r)
inversions = inversions + MERGE-INVERSIONS(A, p, q, r)
return inversions
MERGE-INVERSIONS(A, p, q, r)
n[1] = q - p + 1
n[2] = r - q
let L[1..n[1] + 1] and R[1..n[2] + 1] be new arrays
for i = 1 to n[1]
L[i] = A[p + i - 1]
for j = 1 to n[2]
R[j] = A[q + j]
L[n[1] + 1] = ∞
L[n[2] + 1] = ∞
i = 1
j = 1
inversions = 0
for k = p to r
if R[j] < L[i]
inversions = inversions + n[1] - i + 1
A[k] = R[j]
j = j + 1
else A[k] = L[i]
i = i + 1
return inversions
The initial call is COUNT-INVERSIONS(A,1,n)\text{COUNT-INVERSIONS}(A, 1, n)COUNT-INVERSIONS(A,1,n).
In MERGE-INVERSIONS\text{MERGE-INVERSIONS}MERGE-INVERSIONS, whenever R[j]R[j]R[j] is exposed and a value greater than R[j]R[j]R[j] becomes exposed in the LLL array, we increase inersions by the number of remaining elements in LLL. Then because R[j+1]R[j + 1]R[j+1] becomes exposed, R[j]R[j]R[j] can never be exposed again. We don’t have to worry about merge-inversions involving the sentinel ∞\infty∞ in RRR, since no value in LLL will be greater than ∞\infty∞.
Since we have added only a constant amount of additional work to each procedure call and to each iteration of the last for loop of the merging procedure, the total running time of the above pseudocode is the same as for merge sort: Θ(nlgn)\Theta(n\lg n)Θ(nlgn).
2.1-1
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT\text{INSERTION-SORT}INSERTION-SORT on the array A=⟨31,41,59,26,41,58⟩A = \langle 31, 41, 59, 26, 41, 58 \rangleA=⟨31,41,59,26,41,58⟩.
\begin{align}
A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\
A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\
A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\
A & = \langle 26, 31, 41, 59, 41, 58 \rangle \\
A & = \langle 26, 31, 41, 41, 59, 58 \rangle \\
A & = \langle 26, 31, 41, 41, 58, 59 \rangle
\end{align}
2.1-2
Rewrite the INSERTION-SORT\text{INSERTION-SORT}INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] < key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
2.1-3
Consider the searching problem:
Input: A sequence of nnn numbers A=⟨a1,a2,…,an⟩A = \langle a_1, a_2, \ldots, a_n \rangleA=⟨a1,a2,…,an⟩ and a value vvv.
Output: An index iii such that v=A[i]v = A[i]v=A[i] or the special value NIL\text{NIL}NIL if vvv does not appear in AAA.
Write pseudocode for linear search, which scans through the sequence, looking for vvv. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
LINEAR-SEARCH(A, v)
for i = 1 to A.length
if A[i] == v
return i
return NIL
Loop invariant: At the start of each iteration of the for loop, the subarray A[1..i−1]A[1..i - 1]A[1..i−1] consists of elements that are different than vvv.
Initialization: Initially the subarray is the empty array, so the prove is trivial.
Maintenance: On each step, we know that A[1..i−1]A[1..i - 1]A[1..i−1] does not contain vvv. We compare it with A[i]A[i]A[i]. If they are the same, we return iii, which is a correct result. Otherwise, we continue to the next step. We have already insured that A[1..i−1]A[1..i - 1]A[1..i−1] does not contain vvv and that A[i]A[i]A[i] is different from vvv, so this step preserves the invariant.
Termination: The loop terminates when i>A.lengthi > A.lengthi>A.length. Since iii increases by 111 and i>A.lengthi > A.lengthi>A.length, we know that all the elements in AAA have been checked and it has been found that vvv is not among them. Thus, we return NIL\text{NIL}NIL.
2.1-4
Consider the problem of adding two nnn-bit binary integers, stored in two nnn-element arrays AAA and BBB. The sum of the two integers should be stored in binary form in an (n+1)(n + 1)(n+1)-element array CCC. State the problem formally and write pseudocode for adding the two integers.
Input: An array of booleans A=⟨a1,a2,…,an⟩A = \langle a_1, a_2, \ldots, a_n \rangleA=⟨a1,a2,…,an⟩ and an array of booleans B=⟨b1,b2,…,bn⟩B = \langle b_1, b_2, \ldots, b_n \rangleB=⟨b1,b2,…,bn⟩, each representing an integer stored in binary format (each digit is a number, either 000 or 111, least-significant digit first) and each of length nnn.
Output: An array C=⟨c1,c2,…,cn+1⟩C = \langle c_1, c_2, \ldots, c_{n + 1} \rangleC=⟨c1,c2,…,cn+1⟩ such that C′=A′+B′C' = A' + B'C′=A′+B′ where A′A'A′, B′B'B′ and C′C'C′ are the integers, represented by AAA, BBB and CCC.
ADD-BINARY(A, B)
C = new integer[A.length + 1]
carry = 0
for i = 1 to A.length
C[i] = (A[i] + B[i] + carry) % 2 // remainder
carry = (A[i] + B[i] + carry) / 2 // quotient
C[i] = carry
return C
2.2-1
Express the function n3/1000−100n2−100n+3nn^3 / 1000 - 100n^2 - 100n + 3nn3/1000−100n2−100n+3n in terms of Θ\ThetaΘ-notation.
Θ(n3)\Theta(n^3)Θ(n3).
2.2-2
Consider sorting nnn numbers stored in array AAA by first finding the smallest element of AAA and exchanging it with the element in A[1]A[1]A[1]. Then find the second smallest element of AAA, and exchange it with A[2]A[2]A[2]. Continue in this manner for the first n−1n - 1n−1 elements of AAA. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n−1n - 1n−1 elements, rather than for all nnn elements? Give the best-case and worst-case running times of selection sort in Θ\ThetaΘ-notation.
SELECTION-SORT(A)
n = A.length
for j = 1 to n - 1
smallest = j
for i = j + 1 to n
if A[i] < A[smallest]
smallest = i
exchange A[j] with A[smallest]
The algorithm maintains the loop invariant that at the start of each iteration of the outer for loop, the subarray A[1..j−1]A[1..j - 1]A[1..j−1] consists of the j−1j - 1j−1 smallest elements in the array A[1..n]A[1..n]A[1..n], and this subarray is in sorted order. After the first n−1n - 1n−1 elements, the subarray A[1..n]A[1..n]A[1..n] contains the smallest n−1n - 1n−1 elements, sorted, and therefore element A[n]A[n]A[n] must be the largest element.
The running time of the algorithm is Θ(n2)\Theta(n^2)Θ(n2) for all cases.
2.2-3
Consider linear search again (see Exercise 2.1-3). How many elements of the in- put sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ\ThetaΘ-notation? Justify your answers.
If the element is present in the sequence, half of the elements are likely to be checked before it is found in the average case. In the worst case, all of them will be checked. That is, n/2n / 2n/2 checks for the average case and nnn for the worst case. Both of them are Θ(n)\Theta(n)Θ(n).
2.2-4
How can we modify almost any algorithm to have a good best-case running time?
Modify the algorithm so it tests whether the input satisfies some special-case condition and, if it does, output a pre-computed answer. The best-case running time is generally not a good measure of an algorithm.
2.3-1
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A=⟨3,41,52,26,38,57,9,49⟩A = \langle 3, 41, 52, 26, 38, 57, 9, 49 \rangleA=⟨3,41,52,26,38,57,9,49⟩.
[3][41][52][26][38][57][9][49] [3] \quad [41] \quad [52] \quad [26] \quad [38] \quad [57] \quad [9] \quad [49] [3][41][52][26][38][57][9][49]
↓ \downarrow ↓
[3∣41][26∣52][38∣57][9∣49] [3|41] \quad [26| 52] \quad [38|57] \quad [9|49] [3∣41][26∣52][38∣57][9∣49]
↓ \downarrow ↓
[3∣26∣41∣52][9∣38∣49∣57] [3|26|41|52] \quad [9 |38|49|57] [3∣26∣41∣52][9∣38∣49∣57]
↓ \downarrow ↓
[3∣9∣26∣38∣41∣49∣52∣57] [3|9|26|38|41|49|52|57] [3∣9∣26∣38∣41∣49∣52∣57]
2.3-2
Rewrite the MERGE\text{MERGE}MERGE procedure so that it does not use sentinels, instead stopping once either array LLL or RRR has had all its elements copied back to AAA and then copying the remainder of the other array back into AAA.
MERGE(A, p, q, r)
n[1] = q - p + 1
n[2] = r - q
let L[1..n[1]] and R[1..n[2]] be new arrays
for i = 1 to n[1]
L[i] = A[p + i - 1]
for j = 1 to n[2]
R[j] = A[q + j]
i = 1
j = 1
for k = p to r
if i > n[1]
A[k] = R[j]
j = j + 1
else if j > n[2]
A[k] = L[i]
i = i + 1
else if L[i] ≤ R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
2.3-3
Use mathematical induction to show that when nnn is an exact power of 222, the solution of the recurrence
T(n)={2if n=2,2T(n/2)if n=2k,for k>1 T(n) = \begin{cases} 2 & \text{if } n = 2, \\\\ 2T(n / 2) & \text{if } n = 2^k, \text{for } k > 1 \end{cases} T(n)=⎩⎪⎨⎪⎧22T(n/2)if n=2,if n=2k,for k>1
is T(n)=nlgnT(n) = n\lg nT(n)=nlgn.
The base case is when n=2n = 2n=2, and we have nlgn=2lg2=2⋅1=2n\lg n = 2\lg 2 = 2 \cdot 1 = 2nlgn=2lg2=2⋅1=2.
For the inductive step, our inductive hypothesis is that T(n/2)=(n/2)lg(n/2)T(n / 2) = (n / 2)\lg(n / 2)T(n/2)=(n/2)lg(n/2). Then
\begin{align}
T(n) & = 2T(n / 2) + n \\
& = 2(n / 2) \lg(n / 2) + n \\
& = n(\lg n - 1) + n \\
& = n\lg n - n + n \\
& = n\lg n,
\end{align}
which completes the inductive proof for exact powers of 222.
2.3-4
We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n]A[1..n]A[1..n], we recursively sort A[1..n−1]A[1..n - 1]A[1..n−1] and then insert A[n]A[n]A[n] into the sorted array A[1..n−1]A[1..n - 1]A[1..n−1]. Write a recurrence for the running time of this recursive version of insertion sort.
Since it takes Θ(n)\Theta(n)Θ(n) time in the worst case to insert A[n]A[n]A[n] into the sorted array A[1..n−1]A[1..n - 1]A[1..n−1], we get the recurrence
T(n)={Θ(1)if n=1,T(n−1)+Θ(n)if n>1. T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\\\ T(n - 1) + \Theta(n) & \text{if } n > 1. \end{cases} T(n)=⎩⎪⎨⎪⎧Θ(1)T(n−1)+Θ(n)if n=1,if n>1.
Although the exercise does not ask you to solve this recurrence, its solution is T(n)=Θ(n2)T(n) = \Theta(n^2)T(n)=Θ(n2).
2.3-5
Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence AAA is sorted, we can check the midpoint of the sequence against vvv and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ(lgn)\Theta(\lg n)Θ(lgn).
Procedure BINARY-SEARCH\text{BINARY-SEARCH}BINARY-SEARCH takes a sorted array AAA, a value vvv, and a range [low..high][low..high][low..high] of the array, in which we search for the value vvv. The procedure compares to the array entry at the midpoint of the range and decides to eliminate half the range from further consideration. We give both iterative and recursive versions, each of which returns either an index iii such that A[i]=vA[i] = vA[i]=v, or NIL\text{NIL}NIL if no entry of A[low..high]A[low..high]A[low..high] contains the value vvv. The initial call to either version should have the parameters AAA, vvv, 111, nnn.
ITERATIVE-BINARY-SEARCH(A, v, low, high)
while low ≤ high
mid = floor((low + high) / 2)
if v == A[mid]
return mid
else if v > A[mid]
low = mid + 1
else high = mid - 1
return NIL
RECURSIVE-BINARY-SEARCH(A, v, low, high)
if low > high
return NIL
mid = floor((low + high) / 2)
if v == A[mid]
return mid
else if v > A[mid]
return RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
else return RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)
Both procedures terminate the search unsuccessfully when the range is empty (i.e., low>highlow > highlow>high) and terminate it successfully if the value vvv has been found. Based on the comparison of vvv to the middle element in the searched range, the search continues with the range halved. The recurrence for these procedures is therefore T(n)=T(n/2)+Θ(1)T(n) = T(n / 2) + \Theta(1)T(n)=T(n/2)+Θ(1), whose solution is T(n)=Θ(lgn)T(n) = \Theta(\lg n)T(n)=Θ(lgn).
2.3-6
Observe that the while loop of lines 5–7 of the INSERTION-SORT\text{INSERTION-SORT}INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[i..j−1]A[i..j - 1]A[i..j−1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(nlgn)\Theta(n\lg n)Θ(nlgn)?
The while loop of lines 5–7 of procedure INSERTION-SORT\text{INSERTION-SORT}INSERTION-SORT scans backward through the sorted array A[1..j−1]A[1..j - 1]A[1..j−1] to find the appropriate place for A[j]A[j]A[j]. The hitch is that the loop not only searches for the proper place for A[j]A[j]A[j], but that it also moves each of the array elements that are bigger than A[j]A[j]A[j] one position to the right (line 6). These movements can take as much as Θ(j)\Theta(j)Θ(j) time, which occurs when all the j−1j - 1j−1 elements preceding A[j]A[j]A[j] are larger than A[j]A[j]A[j]. We can use binary search to improve the running time of the search to Θ(lgj)\Theta(\lg j)Θ(lgj), but binary search will have no effect on the running time of moving the elements. Therefore, binary search alone cannot improve the worst-case running time of INSERTION-SORT\text{INSERTION-SORT}INSERTION-SORT to Θ(nlgn)\Theta(n\lg n)Θ(nlgn).
2.3-7 ⋆\star⋆
Describe a Θ(nlgn)\Theta(n\lg n)Θ(nlgn)-time algorithm that, given a set SSS of nnn integers and another integer xxx, determines whether or not there exist two elements in SSS whose sum is exactly xxx.
The following algorithm solves the problem:
- Sort the elements in SSS.
- Form the set KaTeX parse error: Expected '}', got 'EOF' at end of input: …\\{z: z = x - y for some KaTeX parse error: Expected 'EOF', got '}' at position 10: y \in S\\}̲.
- Sort the elements in S′S'S′.
- Merge the two sorted sets SSS and S′S'S′.
- There exist two elements in SSS whose sum is exactly xxx if and only if the same value appears in consecutive positions in the merged output.
To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in SSS whose sum is exactly xxx if and only if the same value appears twice in the merged output.
Suppose that some value www appears twice. Then www appeared once in SSS and once in S′S'S′. Because www appeared in S′S'S′, there exists some y∈Sy \in Sy∈S such that w=x−yw = x - yw=x−y, or x=w+yx = w + yx=w+y. Since w∈Sw \in Sw∈S, the elements www and yyy are in SSS and sum to xxx.
Conversely, suppose that there are values w,y∈Sw, y \in Sw,y∈S such that w+y=xw + y = xw+y=x. Then, since x−y=wx - y = wx−y=w, the value www appears in S′S'S′. Thus, www is in both SSS and S′S'S′, and so it will appear twice in the merged output.
Steps 1 and 3 require Θ(nlgn)\Theta(n\lg n)Θ(nlgn) steps. Steps 2, 4, 5, and 6 require O(n)O(n)O(n) steps. Thus the overall running time is O(nlgn)O(n\lg n)O(nlgn).
A reader submitted a simpler solution that also runs in Θ(nlgn)\Theta(n\lg n)Θ(nlgn) time. First, sort the elements in SSS, taking Θ(nlgn)\Theta(n\lg n)Θ(nlgn) time. Then, for each element yyy in SSS, perform a binary search in SSS for x−yx - yx−y. Each binary search takes O(lgn)O(\lg n)O(lgn) time, and there are are most nnn of them, and so the time for all the binary searches is O(nlgn)O(n\lg n)O(nlgn). The overall running time is Θ(nlgn)\Theta(n\lg n)Θ(nlgn).
Another reader pointed out that since SSS is a set, if the value x/2x / 2x/2 appears in SSS, it appears in SSS just once, and so x/2x / 2x/2 cannot be a solution.
3.1-1
Let f(n)+g(n)f(n) + g(n)f(n)+g(n) be asymptotically nonnegative functions. Using the basic definition of Θ\ThetaΘ-notation, prove that max(f(n),g(n))=Θ(f(n)+g(n))\max(f(n), g(n)) = \Theta(f(n) + g(n))max(f(n),g(n))=Θ(f(n)+g(n)).
First, let’s clarify what the function max(f(n),g(n))\max(f(n), g(n))max(f(n),g(n)) is. Let’s define the function h(n)=max(f(n),g(n))h(n) = \max(f(n), g(n))h(n)=max(f(n),g(n)). Then
h(n)={f(n) if f(n)≥g(n),g(n) if f(n)<g(n). h(n) = \begin{cases} f(n) & \text{ if } f(n) \ge g(n), \\\\ g(n) & \text{ if } f(n) < g(n). \end{cases} h(n)=⎩⎪⎨⎪⎧f(n)g(n) if f(n)≥g(n), if f(n)<g(n).
Since f(n)f(n)f(n) and g(n)g(n)g(n) are asymptotically nonnegative, there exists n0n_0n0 such that f(n)≥0f(n) \ge 0f(n)≥0 and g(n)≥0g(n) \ge 0g(n)≥0 for all n≥n0n \ge n_0n≥n0. Thus for n≥n0n \ge n_0n≥n0 , f(n)+g(n)≥f(n)≥0f(n) + g(n) \ge f(n) \ge 0f(n)+g(n)≥f(n)≥0 and f(n)+g(n)≥g(n)≥0f(n) + g(n) \ge g(n) \ge 0f(n)+g(n)≥g(n)≥0. Since for any particular nnn, h(n)h(n)h(n) is either f(n)f(n)f(n) or g(n)g(n)g(n), we have f(n)+g(n)≥h(n)≥0f(n) + g(n) \ge h(n) \ge 0f(n)+g(n)≥h(n)≥0, which shows that
h(n)=max(f(n),g(n))≤c2(f(n)+g(n))h(n) = \max(f(n), g(n)) \le c_2(f(n) + g(n))h(n)=max(f(n),g(n))≤c2(f(n)+g(n))
for all n≥n0n \ge n_0n≥n0 (with c2=1c_2 = 1c2=1 in the definition of Θ\ThetaΘ).
Similarly, since for any particular nnn, h(n)h(n)h(n) is the larger of f(n)f(n)f(n) and g(n)g(n)g(n), we have for all n≥n0n \ge n_0n≥n0, 0≤f(n)≤h(n)0 \le f(n) \le h(n)0≤f(n)≤h(n) and 0≤g(n)≤h(n)0 \le g(n) \le h(n)0≤g(n)≤h(n). Adding these two inequalities yields 0≤f(n)+g(n)≤2h(n)0 \le f(n) + g(n) \le 2h(n)0≤f(n)+g(n)≤2h(n), or equivalently 0≤(f(n)+g(n))/2≤h(n)0 \le (f(n) + g(n)) / 2 \le h(n)0≤(f(n)+g(n))/2≤h(n), which shows that
h(n)=max(f(n),g(n))≥c1(f(n)+g(n))h(n) = \max(f(n), g(n)) \ge c_1(f(n) + g(n))h(n)=max(f(n),g(n))≥c1(f(n)+g(n))
for all n≥n0n \ge n_0n≥n0 (with c1=1/2c_1 = 1 / 2c1=1/2 in the definition of Θ\ThetaΘ).
3.1-2
Show that for any real constants aaa and bbb, where b>0b > 0b>0,
(3.2)(n+a)b=Θ(nb).(n + a)^b = \Theta(n^b). \tag{3.2}(n+a)b=Θ(nb).(3.2)
To show that (n+a)b=Θ(nb)(n + a)^b = \Theta(n^b)(n+a)b=Θ(nb), we want to find constants c1,c2,n0>0c_1, c_2, n_0 > 0c1,c2,n0>0 such that 0≤c1nb≤(n+a)b≤c2nb0 \le c_1 n^b \le (n + a)^b \le c_2 n^b0≤c1nb≤(n+a)b≤c2nb for all n≥n0n \ge n_0n≥n0.
Note that
\begin{align}
n + a & \le n + |a| & \\
& \le 2n & \text{ when } |a| \le n,
\end{align}
and
\begin{align}
n + a & \ge n - |a| & \\
& \ge \frac{1}{2}n & \text{ when } |a| \le \frac{1}{2}n.
\end{align}
Thus, when n≥2∣a∣n \ge 2|a|n≥2∣a∣,
0≤12n≤n+a≤2n.0 \le \frac{1}{2}n \le n + a \le 2n.0≤21n≤n+a≤2n.
Since b>0b > 0b>0, the inequality still holds when all parts are raised to the power bbb:
\begin{align}
0 \le \Big(\frac{1}{2}n\Big)^b & \le (n + a)^b \le (2n)^b, \\
0 \le \Big(\frac{1}{2}\Big)^b n^b & \le (n + a)^b \le 2^b n^b.
\end{align}
Thus, c1=(1/2)bc_1 = (1 / 2)^bc1=(1/2)b, c2=2bc_2 = 2^bc2=2b, and n0=2∣a∣n_0 = 2|a|n0=2∣a∣ satisfy the definition.
3.1-3
Explain why the statement, ‘‘The running time of algorithm AAA is at least O(n2)O(n^2)O(n2),’’ is meaningless.
Let the running time be T(n)T(n)T(n). T(n)≥O(n2)T(n) \ge O(n^2)T(n)≥O(n2) means that T(n)≥f(n)T(n) \ge f(n)T(n)≥f(n) for some function f(n)f(n)f(n) in the set O(n2)O(n^2)O(n2). This statement holds for any running time T(n)T(n)T(n), since the function g(n)=0g(n) = 0g(n)=0 for all nnn is in O(n2)O(n^2)O(n2), and running times are always nonnegative. Thus, the statement tells us nothing about the running time.
3.1-4
Is 2n+1=O(2n)2^{n + 1} = O(2^n)2n+1=O(2n)? Is 22n=O(2n)2^{2n} = O(2^n)22n=O(2n)?
2n+1=O(2n)2^{n + 1} = O(2^n)2n+1=O(2n), but 22n≠O(2n)2^{2n} \ne O(2^n)22n̸=O(2n).
-
To show that 2n+1=O(2n)2^{n + 1} = O(2^n)2n+1=O(2n), we must find constants ccc; n0>0n_0 > 0n0>0 such that
0≤2n+1≤c⋅2n for all n≥n0. 0 \le 2^{n + 1} \le c \cdot 2^n \text{ for all } n \ge n_0. 0≤2n+1≤c⋅2n for all n≥n0.
Since 2n+1=2⋅2n2^{n + 1} = 2 \cdot 2^n2n+1=2⋅2n for all nnn, we can satisfy the definition with c=2c = 2c=2 and n0=1n_0 = 1n0=1.
-
To show that 22n≠O(2n)2^{2n} \ne O(2^n)22n̸=O(2n), assume there exist constants c,n0>0c, n_0 > 0c,n0>0 such that
0≤22n≤c⋅2n for all n≥n0. 0 \le 2^{2n} \le c \cdot 2^n \text{ for all } n \ge n_0. 0≤22n≤c⋅2n for all n≥n0.
Then 22n=2n⋅2n≤c⋅2n⇒2n≤c2^{2n} = 2^n \cdot 2^n \le c \cdot 2^n \Rightarrow 2^n \le c22n=2n⋅2n≤c⋅2n⇒2n≤c. But no constant is greater than all 2n2^n2n, and so the assumption leads to a contradiction.
3.1-5
Prove Theorem 3.1.
The theorem states:
For any two functions f(n)f(n)f(n) and g(n)g(n)g(n), we have f(n)=Θ(g(n))f(n) = \Theta(g(n))f(n)=Θ(g(n)) if and only if f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) and f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n)).
From f=Θ(g(n))f = \Theta(g(n))f=Θ(g(n)), we have that
0≤c1g(n)≤f(n)≤c2g(n) for n>n0.0 \le c_1 g(n) \le f(n) \le c_2g(n) \text{ for } n > n_0.0≤c1g(n)≤f(n)≤c2g(n) for n>n0.
We can pick the constants from here and use them in the definitions of OOO and Ω\OmegaΩ to show that both hold.
From f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n)) and f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)), we have that
\begin{align}
& 0 \le c_3g(n) \le f(n) & \text{ for all } n \ge n_1 \\
\text{and } & 0 \le f(n) \le c_4g(n) & \text{ for all } n \ge n_2.
\end{align}
If we let n3=max(n1,n2)n_3 = \max(n_1, n_2)n3=max(n1,n2) and merge the inequalities, we get
0≤c3g(n)≤f(n)≤c4g(n) for all n>n3.0 \le c_3g(n) \le f(n) \le c_4g(n) \text{ for all } n > n_3.0≤c3g(n)≤f(n)≤c4g(n) for all n>n3.
Which is the definition of Θ\ThetaΘ.
3.1-6
Prove that the running time of an algorithm is Θ(g(n))\Theta(g(n))Θ(g(n)) if and only if its worst-case running time is O(g(n))O(g(n))O(g(n)) and its best-case running time is Ω(g(n))\Omega(g(n))Ω(g(n)).
If TwT_wTw is the worst-case running time and TbT_bTb is the best-case running time, we know that
\begin{align}
& 0 \le c_1g(n) \le T_b(n) & \text{ for } n > n_b \\
\text{and } & 0 \le T_w(n) \le c_2g(n) & \text{ for } n > n_w.
\end{align}
Combining them we get
0≤c1g(n)≤Tb(n)≤Tw(n)≤c2g(n) for n>max(nb,nw).0 \le c_1g(n) \le T_b(n) \le T_w(n) \le c_2g(n) \text{ for } n > \max(n_b, n_w).0≤c1g(n)≤Tb(n)≤Tw(n)≤c2g(n) for n>max(nb,nw).
Since the running time is bound between TbT_bTb and TwT_wTw and the above is the definition of the Θ\ThetaΘ-notation, proved.
3.1-7
Prove o(g(n))∩w(g(n))o(g(n)) \cap w(g(n))o(g(n))∩w(g(n)) is the empty set.
We know that for any c>0c > 0c>0,
\begin{align}
& \exists n_1 > 0: 0 \le f(n) < cg(n) \\
\text{and } & \exists n_2 > 0: 0 \le cg(n) < f(n).
\end{align}
If we pick n0=max(n1,n2)n_0 = \max(n_1, n_2)n0=max(n1,n2), from the problem definition we get
f(n)<cg(n)<f(n).f(n) < cg(n) < f(n).f(n)<cg(n)<f(n).
There is no solutions, which means that the intersection is the empty set.
3.1-8
We can extend our notation to the case of two parameters nnn and mmm that can go to infinity independently at different rates. For a given function g(n,m)g(n, m)g(n,m) we denote O(g(n,m))O(g(n, m))O(g(n,m)) the set of functions:
\begin{align}
O(g(n, m)) = \{f(n, m):
& \text{ there exist positive constants } c, n_0, \text{ and } m_0 \\
& \text{ such that } 0 \le f(n, m) \le cg(n, m) \\
& \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\}
\end{align}Give corresponding definitions for Ω(g(n,m))\Omega(g(n, m))Ω(g(n,m)) and Θ(g(n,m))\Theta(g(n, m))Θ(g(n,m)).
\begin{align}
\Omega(g(n, m)) = \{f(n, m):
& \text{ there exist positive constants } c, n_0, \text{ and } m_0 \\
& \text{ such that } 0 \le cg(n, m) \le f(n, m) \\
& \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\}
\end{align}
\begin{align}
\Theta(g(n, m)) = \{f(n, m):
& \text{ there exist positive constants } c_1, c_2, n_0, \text{ and } m_0 \\
& \text{ such that } 0 \le c_1 g(n, m) \le f(n, m) \le c_2 g(n, m) \\
& \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\}
\end{align}
3.2-1
Show that if f(n)f(n)f(n) and g(n)g(n)g(n) are monotonically increasing functions, then so are the functions f(n)+g(n)f(n) + g(n)f(n)+g(n) and f(g(n))f(g(n))f(g(n)), and if f(n)f(n)f(n) and g(n)g(n)g(n) are in addition nonnegative, then f(n)⋅g(n)f(n) \cdot g(n)f(n)⋅g(n) is monotonically increasing.
\begin{align}
f(m) \le f(n) \quad \text{ for } m \le n \\
g(m) \le g(n) \quad \text{ for } m \le n, \\
\to f(m) + g(m) \le f(n) + g(n),
\end{align}
which proves the first function.
Then
f(g(m))≤f(g(n)) for m≤n.f(g(m)) \le f(g(n)) \text{ for } m \le n.f(g(m))≤f(g(n)) for m≤n.
This is true, since g(m)>g(n)g(m) > g(n)g(m)>g(n) and f(n)f(n)f(n) is monotonically increasing.
If both functions are nonnegative, then we can multiply the two equalities and we get
f(m)⋅g(m)≤f(n)⋅g(n).f(m) \cdot g(m) \le f(n) \cdot g(n).f(m)⋅g(m)≤f(n)⋅g(n).
3.2-2
Prove equation (3.16)\text{(3.16)}(3.16).
\begin{align}
a^{\log_b c} = a^\frac{\log_a c}{\log_a b} = (a^{\log_a c})^{\frac{1}{\log_a b}} = c^{\log_b a}
\end{align}
3.2-3
Prove equation (3.19)\text{(3.19)}(3.19). Also prove that n≠ω(2n)n \ne \omega(2^n)n̸=ω(2n) and n≠o(nn)n \ne o(n^n)n̸=o(nn).
(3.19)lg(n!)=Θ(nlgn)\lg(n!) = \Theta(n\lg n) \tag{3.19}lg(n!)=Θ(nlgn)(3.19)
We use Stirling’s approximation:
\begin{align}
\lg(n!)
& = \lg\Bigg(\sqrt{2\pi n}\Big(\frac{n}{e}\Big)^n\Big(1 + \Theta(\frac{1}{n})\Big)\Bigg) \\
& = \lg\sqrt{2\pi n } + \lg\Big(\frac{n}{e}\Big)^n + \lg\Big(1+\Theta(\frac{1}{n})\Big) \\
& = \Theta(\sqrt n) + n\lg{\frac{n}{e}} + \lg\Big(\Theta(1) + \Theta(\frac{1}{n})\Big) \\
& = \Theta(\sqrt n) + \Theta(n\lg n) + \Theta(\frac{1}{n}) \\
& = \Theta(n\lg n).
\end{align}
The other two are
∀n>3:2n=2⋅2⋅⋯⋅2⎵n times<1⋅2⋅⋯⋅n=n!⇒n!=ω(2n).\forall n > 3: 2^n = \underbrace{2 \cdot 2 \cdot \cdots \cdot 2}_\text{n times} < 1 \cdot 2 \cdot \cdots \cdot n = n! \quad \Rightarrow \quad n! = \omega(2^n).∀n>3:2n=n times
and
∀n>1:n!=1⋅2⋅⋯n<n⋅n⋅⋯⋅n⎵n times=nn⇒n!=o(nn).\forall n > 1 : n! = 1 \cdot 2 \cdot \cdots n < \underbrace{n \cdot n \cdot \cdots \cdot n}_\text{n times} = n^n \quad \Rightarrow \quad n! = o(n^n).∀n>1:n!=1⋅2⋅⋯n<n times
3.2-4 ⋆\star⋆
Is the function ⌈lgn⌉!\lceil \lg n \rceil!⌈lgn⌉! polynomially bounded? Is the function ⌈lglgn⌉!\lceil \lg\lg n \rceil!⌈lglgn⌉! polynomially bounded?
⌈lgn⌉!\lceil \lg n \rceil!⌈lgn⌉! is not polynomially bounded, but ⌈lglgn⌉!\lceil \lg\lg n \rceil!⌈lglgn⌉! is.
Proving that a function f(n)f(n)f(n) is polynomially bounded is equivalent to proving that lg(f(n))=O(lgn)\lg(f(n)) = O(\lg n)lg(f(n))=O(lgn) for the following reasons.
- If fff is polynomially bounded, then there exist constants ccc, kkk, n0n_0n0 such that for all n≥n0n \ge n_0n≥n0, f(n)≤cnkf(n) \le cn^kf(n)≤cnk. Hence, lg(f(n))≤kclgn\lg(f(n)) \le kc\lg nlg(f(n))≤kclgn, which, since ccc and kkk are constants, means that lg(f(n))=O(lgn)\lg(f(n)) = O(\lg n)lg(f(n))=O(lgn).
- Similarly, if lg(f(n)=O(lgn)\lg(f(n) = O(\lg n)lg(f(n)=O(lgn), then fff is polynomially bounded.
In the following proofs, we will make use of the following two facts:
- lg(n!)=Θ(nlgn)\lg(n!) = \Theta(n\lg n)lg(n!)=Θ(nlgn) (by equation (3.19)\text{(3.19)}(3.19)).
- ⌈lgn⌉=Θ(lgn)\lceil \lg n \rceil = \Theta(\lg n)⌈lgn⌉=Θ(lgn), because
- ⌈lgn⌉≥lgn\lceil \lg n \rceil \ge \lg n⌈lgn⌉≥lgn
- ⌈lgn⌉<lgn+1≤2lgn for all n≥2\lceil \lg n \rceil < \lg n + 1 \le 2\lg n \text{ for all } n \ge 2⌈lgn⌉<lgn+1≤2lgn for all n≥2
\begin{align}
\lg(\lceil \lg n \rceil!) & = \Theta(\lceil \lg n \rceil \lg \lceil \lg n \rceil) \\
& = \Theta(\lg n\lg\lg n) \\
& = \omega(\lg n).
\end{align}
Therefore, lg(⌈lgn⌉!)≠O(lgn)\lg(\lceil \lg n \rceil!) \ne O(\lg n)lg(⌈lgn⌉!)̸=O(lgn), and so ⌈lgn⌉!\lceil \lg n \rceil!⌈lgn⌉! is not polynomially bounded.
\begin{align}
\lg(\lceil \lg\lg n \rceil!) & = \Theta(\lceil \lg\lg n \rceil \lg \lceil \lg\lg n \rceil) \\
& = \Theta(\lg\lg n\lg\lg\lg n) \\
& = o((\lg\lg n)^2) \\
& = o(\lg^2(\lg n)) \\
& = o(\lg n).
\end{align}
3.2-5 ⋆\star⋆
Which is asymptotically larger: KaTeX parse error: Expected group after '^' at position 8: \lg(\lg^̲\*n) or KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n)?
KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n) is asymptotically larger because KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n) = \lg….
3.2-6
Show that the golden ratio ϕ\phiϕ and its conjugate ϕ^\hat \phiϕ^ both satisfy the equation x2=x+1x^2 = x + 1x2=x+1.
\begin{align}
\phi^2 - \phi - 1
& = \big(\frac{1 + \sqrt 5}{2}\big)^2 - \frac{1 + \sqrt 5}{2} - 1 \\
& = \frac{1 + 2\sqrt 5 + 5 - 2 - 2\sqrt 5 - 4}{4} \\
& = 0.
\end{align}
\begin{align}
\hat\phi^2 - \hat\phi - 1
& = \big(\frac{1 - \sqrt 5}{2}\big)^2 - \frac{1 - \sqrt 5}{2} - 1 \\
& = \frac{1 - 2\sqrt 5 + 5 - 2 + 2\sqrt 5 - 4}{4} \\
& = 0.
\end{align}
3.2-7
Prove by induction that the iiith Fibonacci number satisfies the equality
Fi=ϕi−ϕ^i5,F_i = \frac{\phi^i - \hat\phi^i}{\sqrt 5},Fi=5
ϕi−ϕ^i, where ϕ\phiϕ is the golden ratio and ϕ^\hat\phiϕ^ is its conjugate.
We have two base cases: i=0i = 0i=0 and i=1i = 1i=1. For i=0i = 0i=0, we have
\frac{\phi^0 - \hat\phi^0}{\sqrt 5}
& = \frac{1 - 1}{\sqrt 5} \\
& = 0 \\
& = F_0,
and for i=1i = 1i=1, we have
\begin{align}
\frac{\phi^1 - \hat\phi^1}{\sqrt 5}
& = \frac{(1 + \sqrt 5) - (1 - \sqrt 5)}{2\sqrt 5} \\
& = \frac{2\sqrt 5}{2\sqrt 5} \\
& = 1 \\
& = F_1.
\end{align}
For the inductive case, the inductive hypothesis is that Fi−1−(ϕi−1−ϕ^i−1)/5F_{i - 1} - (\phi^{i - 1} - \hat\phi^{i - 1}) / \sqrt 5Fi−1−(ϕi−1−ϕ^i−1)/5
F_i & = F_{i - 1} + F_{i - 2} & \text{(equation (3.22)} \\
& = \frac{\phi^{i - 1} - \hat\phi^{i - 1}}{\sqrt 5} + \frac{\phi^{i - 2} - \hat\phi^{i - 2}}{\sqrt 5} & \text{(inductive hypothesis)} \\
& = \frac{\phi^{i - 2}(\phi + 1) - \hat\phi^{i - 2}(\hat\phi + 1)}{\sqrt 5} \\
& = \frac{\phi^{i - 2}\phi^2 - \hat\phi^{i - 2}\hat\phi^2}{\sqrt 5} & \text{(Exercise 3.2-6)} \\
& = \frac{\phi^i - \hat\phi^i}{\sqrt 5}.
3.2-8
Show that klnk=Θ(n)k\ln k = \Theta(n)klnk=Θ(n) implies k=Θ(n/lnn)k = \Theta(n / \ln n)k=Θ(n/lnn).
From the symmetry of Θ\ThetaΘ,
klnk=Θ(n)⇒n=Θ(klnk).k\ln k = \Theta(n) \Rightarrow n = \Theta(k\ln k).klnk=Θ(n)⇒n=Θ(klnk).
Let’s find lnn\ln nlnn,
lnn=Θ(ln(klnk))=Θ(lnk+lnlnk)=Θ(lnk).\ln n = \Theta(\ln(k\ln k)) = \Theta(\ln k + \ln\ln k) = \Theta(\ln k).lnn=Θ(ln(klnk))=Θ(lnk+lnlnk)=Θ(lnk).
Let’s divide the two,
nlnn=Θ(klnk)Θ(lnk)=Θ(klnklnk)=Θ(k).\frac{n}{\ln n} = \frac{\Theta(k\ln k)}{\Theta(\ln k)} = \Theta({\frac{k\ln k}{\ln k}}) = \Theta(k).lnnn=Θ(lnk)Θ(klnk)=Θ(lnkklnk)=Θ(k).
The last step above follows from the property that any polylogarithmic function grows more slowly than any positive polynomial function, i.e., that for constants a,b>0a, b > 0a,b>0, we have lgb=o(na)\lg^b = o(n^a)lgb=o(na). Substitute lgn\lg nlgn for nnn, 222 for bbb, and 111 for aaa, giving lg2(lgn)=o(lgn)\lg^2(\lg n) = o(\lg n)lg2(lgn)=o(lgn).
Therefore, lg(⌈lglgn⌉!)=O(lgn)\lg(\lceil \lg\lg n \rceil!) = O(\lg n)lg(⌈lglgn⌉!)=O(lgn), and so ⌈lglgn⌉!\lceil \lg\lg n \rceil!⌈lglgn⌉! is polynomially bounded.
3-1
Let
p(n)=∑i=0daini,p(n) = \sum_{i = 0}^d a_i n^i,p(n)=i=0∑daini,where ad>0a_d > 0ad>0, be a degree-ddd polynomial in nnn, and let kkk be a constant. Use the definitions of the asymptotic notations to prove the following properties.
a. If k≥dk \ge dk≥d, then p(n)=O(nk)p(n) = O(n^k)p(n)=O(nk).
b. If k≤dk \le dk≤d, then p(n)=Ω(nk)p(n) = \Omega(n^k)p(n)=Ω(nk).
c. If k=dk = dk=d, then p(n)=Θ(nk)p(n) = \Theta(n^k)p(n)=Θ(nk).
d. If k>dk > dk>d, then p(n)=o(nk)p(n) = o(n^k)p(n)=o(nk).
e. If k<dk < dk<d, then p(n)=ω(nk)p(n) = \omega(n^k)p(n)=ω(nk).
Let’s see that p(n)=O(nd)p(n) = O(n^d)p(n)=O(nd). We need do pick c=ad+bc = a_d + bc=ad+b, such that
∑i=0d=adnd+ad−1nd−1+⋯+a1n+a0≤cnd.\sum\limits_{i = 0}^d = a_d n^d + a_{d - 1}n^{d - 1} + \cdots + a_1n + a_0 \le cn^d.i=0∑d=adnd+ad−1nd−1+⋯+a1n+a0≤cnd.
When we divide by ndn^dnd, we get
c=ad+b≥ad+ad−1n+ad−2n2+⋯+a0nd.c = a_d + b \ge a_d + \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.c=ad+b≥ad+nad−1+n2ad−2+⋯+nda0.
and
b≥ad−1n+ad−2n2+⋯+a0nd.b \ge \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.b≥nad−1+n2ad−2+⋯+nda0.
If we choose b=1b = 1b=1, then we can choose n0n_0n0,
n0=max(dad−1,dad−2,…,da0d).n_0 = \max(da_{d - 1}, d\sqrt{a_{d - 2}}, \ldots, d\sqrt[d]{a_0}).n0=max(dad−1,dad−2
Now we have n0n_0n0 and ccc, such that
p(n)≤cndfor n≥n0,p(n) \le cn^d \quad \text{for } n \ge n_0,p(n)≤cndfor n≥n0,
which is the definition of O(nd)O(n^d)O(nd).
By chosing b=−1b = -1b=−1 we can prove the Ω(nd)\Omega(n^d)Ω(nd) inequality and thus the Θ(nd)\Theta(n^d)Θ(nd) inequality.
It is very similar to prove the other inequalities.
3-2
Indicate for each pair of expressions (A,B)(A, B)(A,B) in the table below, whether AAA is OOO, ooo, Ω\OmegaΩ, ω\omegaω, or Θ\ThetaΘ of BBB. Assume that k≥1k \ge 1k≥1, ϵ>0\epsilon > 0ϵ>0, and c>1c > 1c>1 are constants. Your answer should be in the form of the table with ‘‘yes’’ or ‘‘no’’ written in each box.
\begin{array}{ccccccc}
A & B & O & o & \Omega & \omega & \Theta \\
\hline
\lg^k n & n^\epsilon & yes & yes & no & no & no \\
n^k & c^n & yes & yes & no & no & no \\
\sqrt n & n^{\sin n} & no & no & no & no & no \\
2^n & 2^{n / 2} & no & no & yes & yes & no \\
n^{\lg c} & c^{\lg n} & yes & no & yes & no & yes \\
\lg(n!) & \lg(n^n) & yes & no & yes & no & yes
\end{array}
版权声明：本文标题：算法导论第三版参考答案 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1758306143a3084241.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论