《算法導論》第四章-思考題（參考答案）

算法導論（第三版）參考答案：思考題4.1，思考題4.2，思考題4.3，思考題4.4，思考題4.5，思考題4.6

Problem 4.1 (Recurrence examples)

Give asymptotic upper and lower bound for T(n) in each of the following recurrences. Assume that T(n) is constant for n≤2 . Make your bounds as tight as possible, and justify your answers.

1. T(n)=2T(n/2)+n4
2. T(n)=T(7n/10)+n
3. T(n)=16T(n/4)+n2
4. T(n)=7T(n/3)+n2
5. T(n)=7T(n/2)+n2
6. T(n)=2T(n/4)+n√
7. T(n)=T(n−2)+n2

1. 主方法情況三， T(n)=Θ(n4)
2. 主方法情況三， T(n)=Θ(n)
3. 主方法情況二， T(n)=Θ(n2lgn)
4. 主方法情況一， T(n)=Θ(n2)
5. 主方法情況一， T(n)=Θ(nlg27)
6. 主方法情況二， T(n)=Θ(n√lgn)
7. 遞歸樹法，假設n為偶數， T(n)=n2+(n−2)2+(n−4)2+⋯+T(2)=∑n2−1i=0(n−2i)2+T(2)=Θ(n3)

Problem 4.2 (Parameter-passing costs)

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:

1. An array is passed by pointer. Time =Θ(1)
2. An array is passed by copying. Time =Θ(N) , where N is the size of the array.
3. An array is passed by copying only the subrage that might be accessed by the called procedure. Time =Θ(q−p+1) if the subarray A[p…q] is passed.

So:

1. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problems and n be the size of a subproblem.
2. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.

1. 二分查找

   a.

   T(n)=T(n/2)+c=Θ(lgn)

   b.

   T(n)=T(n/2)+cN=2cN+T(n/4)=3cN+T(n/8)=∑lgn−1i=0(2icN/2i)=cNlgn=Θ(nlgn) c.

   T(n)=T(n/2)+cn=Θ(n)

2. 歸并排序

   a.

   T(n)=2T(n/2)+cn=Θ(nlgn)

   b.

   T(n)=2T(n/2)+cn+2N=∑i=0lgn−1(cn+2iN)=∑i=0lgn−1cn+N∑i=0lgn−12i=cnlgn+N2lgn−12−1=cnlgn+nN−N=Θ(nN)=Θ(n2)

   c.

   T(n)=2T(n/2)+cn+2n/2=2T(n/2)+(c+1)n=Θ(nlgn)

Problem 4.3 (More recurrence examples)

Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

1. T(n)=4T(n/3)+nlgn
2. T(n)=3T(n/3)+n/lgn
3. T(n)=4T(n/2)+n2n√
4. T(n)=3T(n/3−2)+n/2
5. T(n)=2T(n/2)+n/lgn
6. T(n)=T(n/2)+T(n/4)+T(n/8)+n
7. T(n)=T(n−1)+1/n
8. T(n)=T(n−1)+lgn
9. T(n)=T(n−2)+1/lgn
10. T(n)=n√T(n√)+n

1. 主方法情況一， T(n)=Θ(nlog34)

2. 利用積分求和的近似

   T(n)=3T(n/3)+nlgn=nΘ(1)+∑i=0log3n−1nlgn−i=nΘ(1)+n∑i=1+lgn−log3nlgn1i=Θ(nlglgn)

   ​

3. 主方法情況三， T(n)=Θ(n2n√)
4. n 足夠大時，可以忽略-1。是以應用主方法情況二，T(n)=Θ(nlgn)
5. 通過積分求和的近似，類似第2問

T(n)=2T(n/2)+nlgn=nΘ(1)+∑i=0lgn−1nlgn−i=nΘ(1)+n∑i=1lgn1i=Θ(nlglgn)

1. 類似于練習4.4-6。 T(n)=Θ(n)
2. 通過積分求和近似。

T(n)=T(n−1)+1/n=1n+1n−1+T(n−2)=∑i=0n−11n−i+Θ(1)=∑i=1n1i+Θ(1)=Θ(lgn)

1. 遞歸樹結構類似第7問

T(n)=lgn+T(n−1)=∑i=0n−1lg(n−i)=∑i=1nlgi+Θ(1)=Θ(lg(n!))=Θ(nlgn)

1. 同樣利用到積分求和的近似

T(n)=1lgn+1lg(n−2)+…+Θ(1)=∑i=0n/2−11lg(n−2i)=∑i=2n1lgi=∑i=1lgn1i=Θ(lglgn)

1. 令 S(n)=T(n)n​ ，則 S(n)=S(n√)+1​ 。考慮 n=2m​ 的情況，有 S(2m)=S(2m/2)+1​ 。令 P(m)=S(2m)​ ，得 P(m)=P(m/2)+1​ 。 根據主定理情況二， P(m)=Θ(lgm)​ 。 則

T(n)=nS(n)=nS(2m)=nP(m)=Θ(nlgm)=Θ(nlglgn)

Problem 4.4 (Fibonacci numbers)

This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) F as

>>F(z)>=∑i=0∞Fizi=0+z+z2+2z3+3z4+5z5+8z6+13z7+21z8+…,>>

where Fi is the i th Fibonacci number.

1. Show that F(z)=z+zF(z)+z2F.
   • Show that

   • >>F(z)>>=z1−z−z2=z(1−ϕz)(1−ϕ^z)=15√(11−ϕz−11−ϕ^z)>>

     where

     >ϕ=1+5√2=1.61803…>ϕ^=1−5√2=−0.61803…>

     1. Show that
     >F(z)=∑i=0∞15√(ϕi−ϕ^i)zi>
     1. Use part (c) to prove that Fi=ϕi/5√ for i>0 , rounded to the nearest integer. (Hint: Observe that |ϕ^|<1 .)

1. ​

z+zF(z)+z2F(Z)==z+z∑i=0∞Fizi+z2∑i=0∞Fizi=z+∑i=1∞Fi−1zi+∑i=2∞Fi−2zi=z+0+∑i=2∞(Fi−1+Fi−2)zi=0+z+∑i=2∞Fizi=F(z)

1. 根據第1問，可得

F(z)=z1−z−z2=z(1−ϕz)(1−ϕ^z)=15√(11−ϕz−11−ϕ^z)(ϕ=1+5√2,ϕ^=1−5√2)

1. 根據幾何級數的性質 11−x=∑∞k=0xk當 |x|<1

F(n)=15√(11−ϕz−11−ϕ^z)=15√(∑i=0∞ϕizi−∑i=0∞ϕ^izi)=∑i=0∞15√(ϕi−ϕ^i)zi

1. Fi=ϕi−ϕ^i5√=ϕi5√−ϕ^i5√ ，又 Fi={0,1,2,3,5,8,13...} 。當 i>0 , |ϕ^|<1 ， 得 |ϕ^i5√|<0.5 。是以對一個整數，加/減去一個小于 0.5 的數，對所得結果舍入到最近的整數即可。

Problem 4.5 (Chip testing)

Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accomodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows.

Chip A says	Chip B says	Conclusion
B is good	A is good	both are good, or both are bad
B is good	A is bad	at least one is bad
B is bad	A is good	at least one is bad
B is bad	A is bad	at least one is bad

1. Show that if more than n/2 chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.

2. Consider the problem of finding a single good chip from among n chips, assuming that more than n/2 of the chips are good. Show that ⌊n/2⌋ pairwise tests are sufficient to reduce the problem to one of nearly half the size.

3. Show that the good chips can be identified with Θ(n) pairwise tests, assuming that more than n/2 chips are good. Give and solve the recurrence that describes the number of tests.

1. 因為好晶片檢測準确，而壞晶片檢測不确定（可能準确，也可能錯誤）。如果好晶片數量少于 n/2 ，則就會有同樣數量的壞晶片，假設跟好晶片表現的一樣（總能準确報告晶片的好壞）。按照這種政策，永遠也沒法區分這兩類的好壞性了。
2. 一種政策：從中取出兩類，每類個 ⌊n/2⌋ 。對這兩類一一對應地比較，隻保留滿足情況一（都報告對方為好晶片）的晶片。也就是說，剔除出去的至少有一個壞的。剩下來的每對隻挑選一個，加上可能為配對的晶片，組成一個新集合。這個集合仍然滿足：超過一半的好晶片，同時規模減半。
3. 第2問的政策遞歸式：

T(n)=T(n/2)+⌊n/2⌋

滿足主方法情況三， T(n)=Θ(n)

Python code

import random

class GoodChip:
    def good(self):
        return True

    def check(self, other):
        return other.good()

class BadChip:
    def good(self):
        return False

    def check(self, other):
        return [True, False][random.randint(, )]

def jig(a, b):
    return [a.check(b), b.check(a)]

def diogenes(chips, verbose = False):
    def find_single(chips):
        if len(chips) <= :
            return chips[]
        else:
            halfpoint = len(chips) // 
            pairs     = zip(chips[:halfpoint], chips[halfpoint:halfpoint * ])
            kept      = [a for (a, b) in pairs if jig(a, b) == [True, True]]

            if len(chips) %  == :
                kept.append(chips[-])

            return find_single(kept)

    good = find_single(chips)
    return [chip for chip in chips if jig(good, chip) == [True, True]]
           

Problem 4.6 (Monge arrays)

An m×n array A of real numbers is a Monge array if for all i,j,k, and l such that 1≤i<k≤m and 1≤j<l≤n , we have

>A[i,j]+a[k,l]≤A[i,l]+A[k,j]>

In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersections of the rows and columns, the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge:

>>10>17>24>11>45>36>7517222813443366131622632195128293417372153232324723634>>

1. Prove that an array is Monge if and only i for all i=1,2,…,m−1, and j=1,2,…,n−1 we have

>A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]>

(Hint: For the “if” part, use induction seperately on rows and columns)

1. The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a).)

>>37>21>53>32>43>2363413212273091532103168>

1. Let f(i) be the index of the column containing the leftmost minimum element of the row i . Prove that f(1)≤f(2)≤…f(m) for any m×n Monge array.
2. Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of an m×n Monge array A :

Construct a submatrix A' of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row in A' . Then compute the leftmost minimum in the odd-numbered rows of A .

Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that the leftmost minimum of the even-numbered rows is known) in O(m+n) time.

1. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m+nlogm) .

1. “僅當”證明，根據定義可以友善地得到。對于“當”的部分

A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]⇓A[i,j]+A[k,l]≤A[i,l]+A[k,j]

對行使用歸納法，證明：

A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]⇓A[i,j]+A[k,j+1]≤A[i,j+1]+A[k,j]

則

A[i,j]+A[k,j+1]≤A[i,j+1]+A[k,j](假設)A[k,j]+A[k+1,j+1]≤A[k,j+1]+A[k+1,j](已知)⇓A[i,j]+A[k,j+1]+A[k,j]+A[k+1,j+1]≤A[i,j+1]+A[k,j]+A[k,j+1]+A[k+1,j]⇓A[i,j]+A[k+1,j+1]≤A[i,j+1]+A[k+1,j]

在此基礎上，同理對列使用歸納法。得證

1. 将第一行第三列元素改為24。

37215332432363413212473091532103168

1. 反證法。若 f(i)>f(j)(i<j) ，則

A[i,f(i)]+A[j,f(j)]<A[i,f(j)]+A[j,f(i)]與A[i,f(j)]+A[j,f(i)]≤A[i,f(i)]+A[j,f(j)]沖突

是以當 i<j ， f(i)≤f(j) 。

1. 利用上述性質

T(m,n)=∑i=0m/2−1(μ2i+2−μ2i+1)=∑i=0m/2−1μ2i+2−∑i=0m/2−1μ2i+m/2=∑i=1m/2μ2i−∑i=0m/2−1μ2i+m/2=μm−μ0+m/2≤n+m/2=O(m+n)

1. ​

T(m)=T(m/2)+cn+m/2=cn+dm/2+cn+dm/4+cn+dm/8+…=∑i=0lgm−1cn+∑i=0lgmdm2i+1=cnlgm+dm∑i=0lgm−112i+1<cnlgm+dm∑i=0∞12i=cnlgm+2dm=O(nlgm+m)

C code

typedef struct array {
    int m;
    int n;
    int step;
    int *data;
} array;

int get(array A, int i, int j) {
    return A.data[((i + ) * A.step - ) * A.n + j];
}

array half(array a) {
    array result = { a.m, a.n, a.step * , a.data };
    return result;
}

int height(array array) {
    return array.m / array.step;
}

int min_index(array A, int row, int left, int right) {
    int min = left;

    for (int i = left; i < right; i++) {
        if (get(A, row, i) < get(A, row, min)) {
            min = i;
        }
    }

    return min;
}

void find_minimums(array A, int *mins) {
    if (height(A) == ) {
        mins[] = min_index(A, , , A.n);
    } else {
        array evens = half(A);
        int even_minimums[height(evens)];

        find_minimums(evens, even_minimums);

        int leftmost = ;

        for (int i = ; i < height(evens); i++) {
            leftmost = min_index(A,  * i, leftmost, even_minimums[i] + );

            mins[ * i]     = leftmost;
            mins[ * i + ] = even_minimums[i];
        }

        if (height(A) % ) {
            mins[height(A) - ] = min_index(A, height(A) - , leftmost, A.n);
        }
    }
}