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:
-
An array is passed by pointer. Time = Θ(1).
-
An array is passed by copying. Time = Θ(N), where N is the size of the array.
-
An array is passed by copying only the subrange that might be accessed by the called procedure. Time = Θ(q - p + 1) if the subarray A[p...q] is passed.
a. 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 problem and n be the size of a subproblem.
b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
-
Θ(n^4)
-
Θ(n)
-
Θ(n^2lgn)
-
Θ(n^2)
-
-
-
Θ(n^3)
An array A[1...n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0...n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n) time.
- 00000
- 00001
- 00010
- 00011
- 00101
- 00110
- 00111
- 01000
我们用上面的8个数字当作例子，[0，8]缺4. <br >
1.第一次迭代发现最末位1出现4次0出现3次，所以missnum的最后一位是4，排除掉末位为1的数字
2.然后一次次迭代
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:
-
An array is passed by pointer. Time = Θ(1).
-
An array is passed by copying. Time = Θ(N), where N is the size of the array.
-
An array is passed by copying only the subrange that might be accessed by the calledprocedure. Time = Θ(q - p + 1) if the subarray A[p...q] is passed.
a. 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 problem and n be the size of a subproblem.
b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
a. <br >
-
T(n) = T(n/2) + 2, O(lgN)
-
T(n) = T(n/2) + N, O(NlgN)
-
T(n) = T(n/2) + n, O(N)
b.
a. <br >
b. <br >
c. <br >
d. <br >
e. <br > The same as b
f. <br >
g. <br >
h. <br >
i. <br >
j. <br >
This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.21). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) F as
a. Show that
b. Show that
c. Show that Show that
d. Prove that for i > 0 , rounded to the nearest integer.
e. Prove that for i ≥ 0.
a.
b. 这个结论的证明还是很straight-forward的，就不写公式啦.
c.
d.
Professor Diogenes has n supposedly identical VLSI[1] chips that in principle are capable of testing each other. The professor's test jig accommodates 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 answer of a bad chip cannot be trusted. 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 |
a. 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.
b. 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.
c. Show that the good chips can be identified with Θ(n) pairwise tests, assuming that more than n/2 of the chips are good. Give and solve the recurrence that describes the number of tests.
中文版
a. 如果超过一半是坏的，那么我们可以从这些坏的中取出一组数量和好的一样多的，他们的表现能和好的一样.
b. 将所有的芯片两两配对，如果报告是both are good or bad,那么就从中随机选一个留下来，否则全部扔掉. 一直这样递归下去，最后剩下的是好的.
c. T(n) = T(n/2)+n/2,是Θ(n)的.
English Version
a. consider the situation that at least half chips are bad. Denote good chip number is N. We can choice more than N bad chips, and make them act as same as GOOD one. In this situation, we cannot distinguish whether is GOOD or BAD.(The BAD chips are always major and perfectly confuse information GOOD chips make)
b. Let make floor(N / 2) pairs arbitrarily. We focus the pairs that both of it report opponent is GOOD. Because at least half chips are GOOD, the pairs both report opponent is GOOD contains at least half GOOD-GOOD pairs. Next, we discard one chip of the GOOD-GOOD pair, per every GOOD-GOOD pairs. After all, we operate the remained chips as same as this action.(make pairs -> focus GOOD-GOOD reported pairs -> discard one chip per pairs) We can decrease the target chips by half by discarding, and after discarding we can still assure that target chips contains at least half GOOD chips. As a conclusion, if we make this actions till the last chip remained, the last must be GOOD.
c. The recurrence is
T(n) = T(n / 2) + n / 2
This is Θ(n) admittedly.
日本語版
a. 過半数のチップがbadの時、goodのチップより多くのbadチップに、goodチップと同じ挙動をしてもらえばよい。 そのとき、判別者はどれがgoodでどれがbadチップなのかを判別できない。
b. 任意にfloor(N / 2)ペア組んで、その中で「どちらもGOOD」のペアに着目する。この時、必ず過半数のペアはGOOD-GOODである(つまり、BAD-BADよりもGOOD-GOODの方が必ず多い) 次に、その「どちらもGOOD」の各ペアのうち片方のチップを除外する。この操作後でも、着目するチップのうち、GOODチップはBADチップより必ず多くなる。 よって、その半分にする作業を最後の1つになるまで繰り返せば、残ったチップはGOODだと確定する。(常にGOODチップは BADチップより多いため)
c. T(n)は、n / 2回のペア判別と捨てるを行った後、T(n / 2)の計算に移るので、漸化式は
T(n) = T(n / 2) + n / 2
この漸化式は明らかに、Θ(n)の式となる。
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 the columns, the sum of the upper-left and lower-right elements is less or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge:
a. Prove that an array is Monge if and only if for all i = 1,2,...,m-1 and j = 1,2,...,n- 1, we have <br > A[i, j] + A[i + 1, j + 1] ≤ A[i, j + 1] + A[i + 1, j]. <br > Note (For the "only if" part, use induction separately on rows and columns.)
b. The following array is not Monge. Change one element in order to make it Monge.
c. Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove that f(1) ≤ f(2) ≤ ··· ≤ f(m) for any m × n Monge array.
d. Here is a description of a divide-and-conquer algorithm that computes the left-most minimum element in each row of an m × n Monge array A: <br > Construct a submatrix A′ of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row of A′. Then compute the leftmost minimum in the odd-numbered rows of A. <br > 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.
e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m + n log m).
a.
b.
c. 反证法
如果i < j,f(i) >= f(j)
A[i,f(j)]+A[j,f(i))] <= A[i,f(i)]+A[j,f(j)] 但是A[i,f(i)]和A[j,f(j)]是两行最小的元素，等式不成立.
**d.**根据c可以知道第i行的左端最小值落在f(i-1)和f(i+1)之间. 总共有n/2个奇数行，总共需要比较m次，所以是O(m+n).
e. T(m) = T(m/2) + cn + dm = O(nlgm + m)
Follow @louis1992 on github to help finish this task.