Skip to content

Latest commit

 

History

History
249 lines (151 loc) · 15.5 KB

problem.md

File metadata and controls

249 lines (151 loc) · 15.5 KB
Raw

Problems 1 : Recurrence examples

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

Answer

  1. Θ(n^4)

  2. Θ(n)

  3. Θ(n^2lgn)

  4. Θ(n^2)

  7. Θ(n^3)

Problems 2 : Finding the missing integer

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.

Answer

  • 00000
  • 00001
  • 00010
  • 00011
  • 00101
  • 00110
  • 00111
  • 01000

code

我们用上面的8个数字当作例子，[0，8]缺4. <br >

1.第一次迭代发现最末位1出现4次0出现3次，所以missnum的最后一位是4，排除掉末位为1的数字
2.然后一次次迭代

Problems 3 : 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 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.

Answer

a. <br >

  1. T(n) = T(n/2) + 2, O(lgN)

  2. T(n) = T(n/2) + N, O(NlgN)

  3. T(n) = T(n/2) + n, O(N)

b.

Problems 4 : More recurrence examples

a. <br >

b. <br >

c. <br >

d. <br >

e. <br > The same as b

f. <br >

g. <br >

h. <br >

i. <br >

j. <br >

Problems 5 : Fibonacci numbers

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.

Answer

a.

b. 这个结论的证明还是很straight-forward的，就不写公式啦.

c.

d.

e. we had prove it previously

Problems 6 : VLSI chip testing

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.

Answer

a. 如果超过一半是坏的，那么我们可以从这些坏的中取出一组数量和好的一样多的，他们的表现能和好的一样.

b. 将所有的芯片两两配对，如果报告是both are good or bad,那么就从中随机选一个留下来，否则全部扔掉. 一直这样递归下去，最后剩下的是好的.

c. T(n) = T(n/2)+n/2,是Θ(n)的.

Problems 7 : 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 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).

Answer

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)

code

Follow @louis1992 on github to help finish this task.