clrs算法导论题解

online reading:

http://books.google.com/books?id=NLngYyWFl_YC&pg=PA15&dq=introduction+to+algorithms&psp=1&sig=jX-xfEDWJU3PprUwH8Qfxidli6M#PPA382,M1

*******************
chp1
1.2-1
1.2-2
1.2-3
n=15

**************

chp2
2.1-1 to 2.1-4
2.2-* //*: all has been done.

2.2-2

O(n^2),O(n^2)
?2-1

2-2

***************
chp3
3.1-6
***************

chp4

? 4-6

4-7

ab

c:

random select row r1<r2, if f(r1) > f(r2), we will have A[r1, f(r1)]+A[r2,f(r2)]<A[r1, f(r2)]+A[r2,f(r1)], which cause conflict with the condition.

d:

nlogm (similar to quicksort)

+++++++++

chp5

5.4-1

assume 355days/year.

1)178+1 people(1 is yourself).

2)n*n-n>=355*177

++++++++++++++++++++++++
chp6
6.1-*

6.5-*

**************

chp7

7.4-2

7.4-4 ? probability analysis

7.6

if [a1,b1] and [a2,b2] overlap, we set these 2 element as equal.

while quicksorting, put those internals equaling to pivot together in 2 place(head and tail).

aftera round of partition is finished, put those equal ones to the middle.
7.8

*************

chp8

8-6

a,c,d

b ?

*************'

chp10

10.1-*

10.2-1 to 10.2-4

10.2-7

10.2-8

***************

chp12

12.2-2

12.2-3 ？

12.2-6

12.3-3

worst: O(n^2)

best: ?

*************

chp13

13.1-1 ?

13.2-1

//RIGHT-ROTATE(T,y)

x = y.left

y.left = x.right

if(x.right != NIL(T))

p(x.right) =y

p(x) = p(y)

if( p(y) == NIL(T) )

root = x

else

if ( y == p(y).left )

p(y).left = x

else

p(y).right = x

x.right = y

p(y) = x

13.2-2

13.2-3

a: the depth ofa is added by 1.

b: stay the same.

c: substracted by 1.

13.2-4

one right rotation can add one node to the right-going chain, so at most n - 1 right rotations suffice to transform the tree into a right-going chain.

and, left rotation and right rotation are symmetric.

so, for any 2 n-node binary search tree A and B.

A->right-going chain->B can be done in O(n).

13.2-5 ?

******************

chp15

15.4-2

compare xi and yi.

then compare c[i-1,j] and c[i,j-1].

15.4-3

as figure 15.6, we onlyneed Y[7]to store eachrow of the matrix. so that we stores c[i-1,j-1] and c[i-1,j].

and, we only need a integer to store the value c[i,j-1].

*******************

chp18

In a typical B-tree application, the amount of data handled is so large that all the data do not
fit into main memory at once.

18.1-1

18.1-2

18.1-3

3: rooted with 2,3,4

18.1-4

(2t)^h-1

****************

**********************

Givena n*nmatrix, whoes elements are all integers.

now, we need to select n elements in this matrix, so that there are neither 2 elements in a single row nor in a single column, and the sum of

these n elements must be minimum.

skill: substract or add the same integer in a row or column would not change the positions of the elements of the result. so we can modify the

matrix until it contains no negative integers.

*************************

C.1-1

C.1-4

O: for odd;

E: for even

there are 4 cases:

a: O O O

b: O O E => sum is even

c: O E E

d: E E E => sum is even

the chances for a, d to happen are the same.

the chances for b, c to happen are the same.

so the answer is C(100,3)/2

C.1-5