2014/07/04 15:23

# 习题答案

## 2.1-1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORTon the array A = <31, 41, 59, 26, 41, 58>.

31, 41, 59, 26, 41, 58
31, 41, 59, 26, 41, 58
26, 31, 41, 59, 41, 58
26, 31, 41, 41, 59, 58
26, 31, 41, 41, 58, 59


## 2.1-2

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
//Insert A[j] into the sorted sequence A[1..j-1].
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 numbers A = <a1,a2,...,an> and a value v.

Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

for i = 1 to n
if A[i] == v
return i
return NIL


## 2.1-4

Consider the problem of adding twon-bit binary integers, stored in twon-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element arrayC. State the problem formally and write pseudocode for adding the two integers.

Add(A[], B[])
for i = 1 to n + 1
C[i] = 0
for i = 1 to n
C[i] += (A[i] + B[i])
if C[i] == 2
C[i+1] = 1
C[i] = 0
if C[i] == 3
C[i+1] = 1
C[i] = 1


## 2.2-1

Express the function n^3/1000 - 100n^2 - 100n + 3 in terms of Θ-notation.

Θ(n^3)

## 2.2-2

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element inA(1). Then find the second smallest element of A, and exchange it withA(2). Continue in this manner for the first n-1 elements of A. 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-1 elements, rather than for allnelements? Give the best-case and worst-case running times of selection sort in Θ-notation.

Sort(A[])
for i = 1 to A.len - 1			C1 = n-1
min = -∞						C2 = C1
for j = i + 1 to A.len		C3 = ∑(n-i) {i=1 to n-1}
if A[j] < min			C4 = C3
min = A[j]			C5 = ∑(n-i)*Ti {i=1 to n-1}
//Ti则看情况，如果满足条件了就算1,没满足就算0
k = j				C6 = C5
exchange(A[i], A[k])		C7 = n-1


## 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 Θ-notation? Justify your answers.

## 2.2-4

How can we modify almost any algorithm to have a good best-case running time?

## 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>.

## 2.3-2

Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

Merge(A[], p, q, r)
m = q - p + 1
n = r - q
L[1..m] = A[p..q]
R[1..n] = A[q+1..r]
// 复制到两个数组中

i = j = 1
for k = p to r
if i == m + 1   // L用完了，拷贝R
A[k..r] = R[j..n]
break
if j == n + 1   // R用完了，拷贝L
A[k..r] = L[i..m]
break

if L[i] <= R[j]
A[k] = L[i]
i++
else
A[k] = R[j]
j++


## 2.3-3

Use mathematical induction to show that when n is an exact power of 2,the solution of the recurrence

T(n) = / 2				if n = 2
\ 2T(n/2) + n 	if n = 2^k, for k > 1


is

T(n) = nlgn


T(k) = klgk


T(2k) = 2T(k) + 2k
= 2klgk + 2k
= 2k(lgk + lg2) - 2klg2 + 2k
= 2klg2k - 2klg2 + 2k
= 2klg2k + 2k*0.7
= Θ(2klg2k)


## 2.3-4

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1, n-1]. Write a recurrence for the running time of this recursive version of insertion sort.

Sort(A[], i)
if i == 1
return
Sort(A[], i-1)
k = A[i]
for j = i-1 to 1
if A[j] > k
A[j+1] = A[j]
else
break
A[j] = k


## 2.3-5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against 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).

BinarySearch(A[], v)
i = 1
j = n
while i < j
k = (i+j)/2 」(取下整)
if v > A[k]
i = k
continue
else if v < A[i]
j = k
continue
else
return i
return NIL


## 2.3-6

Observe that thewhileloop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1..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)?

INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
i = BinarySearch(A[1..j-1], key)    C1 = ∑lgj {j=2 to n}
//这里有个边界条件，就是i为NIL的情况下，key是大于数组中所有的数呢？还是小于呢？
for k = j to i+1					C2 = ∑(j/2) {j=2 to n}
A[k] = A[k-1]
A[i] = k


## 2.3-7 *

Describe a Θ(nlgn)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

总运行时间 = 排序消耗Θ(nlgn) + 遍历(n)*BinarySearch(lgn)
= Θ(nlgn)


# 问题答案

## 2-1 Insertion sort on small arrays in merge sort

Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n^2) 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/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

a. Show that insertion sort can sort the n/k sublists, each of length k,in Θ(nk) worst-case time.

总运行时间 = n/k * Θ(k^2)
= Θ(nk)


b. Show how to merge the sublists in Θ(nlg(n/k)) worst-case time.

总时间 = n * 树的高度


总运行时间 = n * 树的高度
= n * lg(n/k)
= Θ(nlg(n/k))


c. Given that the modified algorithm runs in Θ(nk + nlg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of Θ-notation?

Θ(nk + nlg(n/k)) >= Θ(nlgn)


k = Θ(lgn)
Θ(nk + nlg(n/k)) = Θ(nlgn + nlg(n/lgn))
= Θ(nlgn)


d. How should we choose k in practice?

运行时间 = C1*nk + C2*nlg(n/k)


## 2-2 Correctness of bubblesort

Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

BUBBLESORT(A)
1	for i = 1 to A.length - 1
2		for j = A.length downto i + 1
3			if A[j]  < A[j+1]
4				exchange A[j] with A[j-1]


a. Let A denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that

A[1] < A[2] < ... < A[n]		(2.3)


where n = 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).

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 thefor loop in lines 1–4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

OK，进入正题

[ 3, 2, 5, 1, 9]
^  ^
[ 3, 2, 5, 1, 9]
^ ←^
[ 3, 2, 1, 5, 9]
^ ←^
[ 3, 1, 2, 5, 9]
^ ←^
[ 1, 3, 2, 5, 9]


d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

## 2-3 Correctness of Horner’s rule

The following code fragment implements Horner’s rule for evaluating a polynomial

P(x) = ∑a[k] * x^k
= a[0] + x(a[1] + x(a[2] + .... x(a[n-1] + xa[n])..)


given the coefficients a[0], a[1]...a[n] and a value for x:

y = 0
for i = n downto 0
y = a[i] + x * y


a. In terms of Θ-notation, what is the running time of this code fragment for Horner’s rule?

Θ(n)，话说我真没想到一个多项式的乘法还有这么多花头

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?

运行时间 = 1 + 2 + ... n+1
= Θ(n^2)


c. Consider the following loop invariant: At the start of each iteration of theforloop of lines 2–3,

y = ∑a[k+i+1]x^k {k = 0 to n-(i+1)}


**Interpret a summation with no terms as equaling 0. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, **

y= ∑a[k]x^k


d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a[0]...a[n].

## 2-4 Inversions

Let A[1..n] be an array of n distinct numbers. If i<j and A[i] > A[j], then the pair (i,j) is called an inversion of A.

a. List the five inversions of the array <2,3,8,6,1>

<8,6> -- (3,4)
<6,1> -- (4,5)
<2,1> -- (1,5)
<3,1> -- (2,5)
<8,1> -- (3,5)


b. What array with elements from the set {1,2,...n} has the most inversions? How many does it have?

<n, n-1,...2,1>


c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

<2,3,8,6,1>
|2不用插，是第一个元素
<2,3,8,6,1>
|3想插一下，但发现2比3小，也不能插
<2,3,8,6,1>
|8也是
<2,3,8,6,1>
|6可以往前面插1格，因为6小于8，发现 逆序对数 = 1
<2,3,6,8,1>
|1可以往前面插4格，1是最小的，发现 逆序对数 = 1 + 4 = 5
<1,2,3,6,8>


d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(nlgn) worst-case time. (Hint:Modify merge sort.)

c问题的答案恰恰是我们所需要的，做一个推论，不只是插入排序，任何一个排序算法的

移动元素步数=逆序对的数目


Merge-Inverse(A[], p, q, r)
m = q - p + 1
n = r - q
L[1..m] = A[p..q]
R[1..n] = A[q+1..r]
// 复制到两个数组中

i = j = 1
x = 0
for k = p to r
if i == m + 1   // L用完了，拷贝R
A[k..r] = R[j..n]
break
if j == n + 1   // R用完了，拷贝L
A[k..r] = L[i..m]
break

if L[i] <= R[j]
A[k] = L[i]
i++
//左边的小于右边，很好，没增加逆序对的数量
else
A[k] = R[j]
j++
// 右边的小于左边，嗯，这就要开始算左边剩的元素数量了
x += (m - i + 1)
return x

Merge-Sort-Inverse(A[],p,r)
x = 0
if p < r
q = (p + r)/2 」
x += Merge-Sort-Inverse(A,p,q)
x += Merge-Sort-Inverse(A,q,r)
x += Merge-Inverse(A,p,q,r)
// 逆序对数量 = 左分支产生的数量 + 右分支产生的数量 + 归并过程中产生的数量
return x


OK!Done!

2 评论
9 收藏
1