算法导论第三版答案

Solution to Exercise2.2-2

S ELECTION-S ORT.A/

n D A:length

for j D1to n 1

smallest D j

for i D j C1to n

if A?i

smallest D i

exchange A?j with A?smallest

The algorithm maintains the loop invariant that at the start of each iteration of the

outer for loop,the subarray A?1::j 1 consists of the j 1smallest elements

in the array A?1::n ,and this subarray is in sorted order.After the?rst n 1

elements,the subarray A?1::n 1 contains the smallest n 1elements,sorted,

and therefore element A?n must be the largest element.

The running time of the algorithm is?.n2/for all cases.

2-2Selected Solutions for Chapter2:Getting Started

A?low::high contains the value .The initial call to either version should have

the parameters A; ;1;n.

I TERATIVE-B INARY-S EARCH.A; ;low;high/

while low high

mid D b.low C high/=2c

if ==A?mid

return mid

elseif >A?mid

low D mid C1

else high D mid 1

return NIL

R ECURSIVE-B INARY-S EARCH.A; ;low;high/

if low>high

return NIL

mid D b.low C high/=2c

if ==A?mid

return mid

elseif >A?mid

return R ECURSIVE-B INARY-S EARCH.A; ;mid C1;high/

else return R ECURSIVE-B INARY-S EARCH.A; ;low;mid 1/

Both procedures terminate the search unsuccessfully when the range is empty(i.e.,

low>high)and terminate it successfully if the value has been found.Based

on the comparison of to the middle element in the searched range,the search

continues with the range halved.The recurrence for these procedures is therefore

T.n/D T.n=2/C?.1/,whose solution is T.n/D?.lg n/.

Selected Solutions for Chapter2:Getting Started2-3 d.We follow the hint and modify merge sort to count the number of inversions in

?.n lg n/time.

To start,let us de?ne a merge-inversion as a situation within the execution of merge sort in which the M ERGE procedure,after copying A?p::q to L and A?q C1::r to R,has values x in L and y in R such that x>y.Consider an inversion.i;j/,and let x D A?i and y D A?j ,so that iy.

We claim that if we were to run merge sort,there would be exactly one merge-inversion involving x and y.To see why,observe that the only way in which array elements change their positions is within the M ERGE procedure.More-over,since M ERGE keeps elements within L in the same relative order to each other,and correspondingly for R,the only way in which two elements can change their ordering relative to each other is for the greater one to appear in L and the lesser one to appear in R.Thus,there is at least one merge-inversion involving x and y.To see that there is exactly one such merge-inversion,ob-serve that after any call of M ERGE that involves both x and y,they are in the same sorted subarray and will therefore both appear in L or both appear in R in any given call thereafter.Thus,we have proven the claim.

We have shown that every inversion implies one merge-inversion.In fact,the correspondence between inversions and merge-inversions is one-to-one.Sup-pose we have a merge-inversion involving values x and y,where x originally was A?i and y was originally A?j .Since we have a merge-inversion,x>y.

And since x is in L and y is in R,x must be within a subarray preceding the subarray containing y.Therefore x started out in a position i preceding y’s original position j,and so.i;j/is an inversion.

Having shown a one-to-one correspondence between inversions and merge-inversions,it suf?ces for us to count merge-inversions.

Consider a merge-inversion involving y in R.Let′be the smallest value in L that is greater than y.At some point during the merging process,′and y will be the“exposed”values in L and R,i.e.,we will have′D L?i and y D R?j in line13of M ERGE.At that time,there will be merge-inversions involving y and L?i ;L?i C1 ;L?i C2 ;:::;L?n1 ,and these n1 i C1merge-inversions will be the only ones involving y.Therefore,we need to detect the?rst time that′and y become exposed during the M ERGE procedure and add the value of n1 i C1at that time to our total count of merge-inversions.

The following pseudocode,modeled on merge sort,works as we have just de-scribed.It also sorts the array A.

C OUNT-I NVERSIONS.A;p;r/

in ersions D0

if p

q D b.p C r/=2c

in ersions D in ersions C C OUNT-I NVERSIONS.A;p;q/

in ersions D in ersions C C OUNT-I NVERSIONS.A;q C1;r/

in ersions D in ersions C M ERGE-I NVERSIONS.A;p;q;r/ return in ersions

2-4Selected Solutions for Chapter2:Getting Started

M ERGE-I NVERSIONS.A;p;q;r/

n1D q p C1

n2D r q

let L?1::n1C1 and R?1::n2C1 be new arrays

for i D1to n1

L?i D A?p C i 1

for j D1to n2

R?j D A?q C j

L?n1C1 D1

R?n2C1 D1

i D1

j D1

in ersions D0

counted D FALSE

for k D p to r

if counted==FALSE and R?j

in ersions D in ersions C n1 i C1

counted D TRUE

if L?i R?j

A?k D L?i

i D i C1

else A?k D R?j

j D j C1

counted D FALSE

return in ersions

The initial call is C OUNT-I NVERSIONS.A;1;n/.

In M ERGE-I NVERSIONS,the boolean variable counted indicates whether we

have counted the merge-inversions involving R?j .We count them the?rst time

that both R?j is exposed and a value greater than R?j becomes exposed in

the L array.We set counted to FALSE upon each time that a new value becomes

exposed in R.We don’t have to worry about merge-inversions involving the

sentinel1in R,since no value in L will be greater than1.

Since we have added only a constant amount of additional work to each pro-

cedure call and to each iteration of the last for loop of the merging procedure,

the total running time of the above pseudocode is the same as for merge sort:

?.n lg n/.

Solution to Exercise3.1-2

To show that.n C a/b D?.n b/,we want to?nd constants c1;c2;n0>0such that

0 c1n b .n C a/b c2n b for all n n0.

Note that

n C a n C j a j

2n when j a j n,

and

n C a n j a j

1

2

n.

Thus,when n 2j a j, 0

1

2n

b

.n C a/b .2n/b;

1

Solution to Exercise3.1-3

Let the running time be T.n/.T.n/ O.n2/means that T.n/ f.n/for some

function f.n/in the set O.n2/.This statement holds for any running time T.n/,

since the function g.n/D0for all n is in O.n2/,and running times are always

nonnegative.Thus,the statement tells us nothing about the running time.

3-2Selected Solutions for Chapter3:Growth of Functions

Solution to Exercise3.2-4

d lg n e?is not polynomially bounded,but d lg lg n e?is.

Proving that a function f.n/is polynomially bounded is equivalent to proving that

lg.f.n//D O.lg n/for the following reasons.

If f is polynomially bounded,then there exist constants c,k,n0such that for all n n0,f.n/ cn k.Hence,lg.f.n// kc lg n,which,since c and k are

constants,means that lg.f.n//D O.lg n/.

Similarly,if lg.f.n//D O.lg n/,then f is polynomially bounded.

In the following proofs,we will make use of the following two facts:

1.lg.n?/D?.n lg n/(by equation(3.19)).

2.d lg n e D?.lg n/,because

d lg n

e lg n

d lg n e

lg.d lg n e?/D?.d lg n e lg d lg n e/

D?.lg n lg lg n/

D!.lg n/:

Therefore,lg.d lg n e?/¤O.lg n/,and so d lg n e?is not polynomially bounded.

lg.d lg lg n e?/D?.d lg lg n e lg d lg lg n e/

D?.lg lg n lg lg lg n/

D o..lg lg n/2/

D o.lg2.lg n//

D o.lg n/:

Selected Solutions for Chapter3:Growth of Functions3-3 The last step above follows from the property that any polylogarithmic function grows more slowly than any positive polynomial function,i.e.,that for constants a;b>0,we have lg b n D o.n a/.Substitute lg n for n,2for b,and1for a,giving lg2.lg n/D o.lg n/.

Therefore,lg.d lg lg n e?/D O.lg n/,and so d lg lg n e?is polynomially bounded.

Solution to Exercise4.2-4

If you can multiply3 3matrices using k multiplications,then you can multiply

n n matrices by recursively multiplying n=3 n=3matrices,in time T.n/D

kT.n=3/C?.n2/.

Using the master method to solve this recurrence,consider the ratio of n log3k

and n2:

If log3k D2,case2applies and T.n/D?.n2lg n/.In this case,k D9and T.n/D o.n lg7/.

If log3k<2,case3applies and T.n/D?.n2/.In this case,k<9and T.n/D o.n lg7/.

If log3k>2,case1applies and T.n/D?.n log3k/.In this case,k>9.

k

3

such integer k is21.

Thus,k D21and the running time is?.n log3k/D?.n log321/D O.n2:80/(since

21 2:77).

log

3

Solution to Exercise4.4-9

T.n/D T.?n/C T..1 ?/n/C cn

We saw the solution to the recurrence T.n/D T.n=3/C T.2n=3/C cn in the text.

This recurrence can be similarly solved.

4-2Selected Solutions for Chapter 4:Divide-and-Conquer

Without loss of generality,let ? 1 ?,so that 0<1 ? 1=2and 1=2 ?<1.

?lg ?C .1 ?/lg .1

?/or

d c

?lg ? .1 ?/

lg .1 ?/:Therefore,T.n/D ?.n lg n/.

Solution to Exercise5.2-1

Since H IRE-A SSISTANT always hires candidate1,it hires exactly once if and only

if no candidates other than candidate1are hired.This event occurs when candi-

date1is the best candidate of the n,which occurs with probability1=n.

H IRE-A SSISTANT hires n times if each candidate is better than all those who were

interviewed(and hired)before.This event occurs precisely when the list of ranks

given to the algorithm is h1;2;:::;n i,which occurs with probability1=n?.

5-2Selected Solutions for Chapter5:Probabilistic Analysis and Randomized Algorithms Thus,

E?X D E

"n X

i D1X i #

D

n

X

i D1

E?X i (linearity of expectation)

D

n

X i D1

1=n

D1;

and so we expect that exactly1customer gets back his own hat.

Note that this is a situation in which the indicator random variables are not inde-pendent.For example,if n D2and X1D1,then X2must also equal1.Con-versely,if n D2and X1D0,then X2must also equal0.Despite the dependence, Pr f X i D1g D1=n for all i,and linearity of expectation holds.Thus,we can use the technique of indicator random variables even in the presence of dependence.

Selected Solutions for Chapter5:Probabilistic Analysis and Randomized Algorithms5-3

D n

2

!

1

2

1 4

:

Thus the expected number of inverted pairs is n.n 1/=4.

Solution to Exercise5.3-4

P ERMUTE-B Y-C YCLIC chooses offset as a random integer in the range1

offset n,and then it performs a cyclic rotation of the array.That is,

B?..i C offset 1/mod n/C1 D A?i for i D1;2;:::;n.(The subtraction

and addition of1in the index calculation is due to the1-origin indexing.If we

had used0-origin indexing instead,the index calculation would have simplied to

B?.i C offset/mod n D A?i for i D0;1;:::;n 1.)

Thus,once offset is determined,so is the entire permutation.Since each value of

offset occurs with probability1=n,each element A?i has a probability of ending

up in position B?j with probability1=n.

This procedure does not produce a uniform random permutation,however,since

it can produce only n different permutations.Thus,n permutations occur with

probability1=n,and the remaining n? n permutations occur with probability0.

Solution to Exercise6.1-1

Since a heap is an almost-complete binary tree(complete at all levels except pos-

sibly the lowest),it has at most2h C1 1elements(if it is complete)and at least

2h 1C1D2h elements(if the lowest level has just1element and the other levels

are complete).

Solution to Exercise6.2-6

If you put a value at the root that is less than every value in the left and right

subtrees,then M AX-H EAPIFY will be called recursively until a leaf is reached.To

make the recursive calls traverse the longest path to a leaf,choose values that make

M AX-H EAPIFY always recurse on the left child.It follows the left branch when

the left child is greater than or equal to the right child,so putting0at the root

and1at all the other nodes,for example,will accomplish that.With such values,

M AX-H EAPIFY will be called h times(where h is the heap height,which is the

number of edges in the longest path from the root to a leaf),so its running time

will be?.h/(since each call does?.1/work),which is?.lg n/.Since we have

a case in which M AX-H EAPIFY’s running time is?.lg n/,its worst-case running

time is .lg n/.

6-2Selected Solutions for Chapter6:Heapsort

Selected Solutions for Chapter6:Heapsort6-3

Solution to Problem6-1

a.The procedures B UILD-M AX-H EAP and B UILD-M AX-H EAP0do not always

create the same heap when run on the same input array.Consider the following

counterexample.

Input array A:

A

B UILD-M AX-H EAP.A/:

A

B UILD-M AX-H EAP0.A/:

A

b.An upper bound of O.n lg n/time follows immediately from there being n 1

calls to M AX-H EAP-I NSERT,each taking O.lg n/time.For a lower bound

6-4Selected Solutions for Chapter6:Heapsort

of .n lg n/,consider the case in which the input array is given in strictly in-

creasing order.Each call to M AX-H EAP-I NSERT causes H EAP-I NCREASE-

K EY to go all the way up to the root.Since the depth of node i is b lg i c,the

total time is

n

X i D1?.b lg i c/

n

X

i Dd n=2e

?.b lg d n=2ec/

n

X

i Dd n=2e

?.b lg.n=2/c/

D

n

X

i Dd n=2e

?.b lg n 1c/

n=2 ?.lg n/

D .n lg n/:

In the worst case,therefore,B UILD-M AX-H EAP0requires?.n lg n/time to build an n-element heap.

Solution to Exercise7.2-3

P ARTITION does a“worst-case partitioning”when the elements are in decreasing

order.It reduces the size of the subarray under consideration by only1at each step,

which we’ve seen has running time?.n2/.

In particular,P ARTITION,given a subarray A?p::r of distinct elements in de-

creasing order,produces an empty partition in A?p::q 1 ,puts the pivot(orig-

inally in A?r )into A?p ,and produces a partition A?p C1::r with only one

fewer element than A?p::r .The recurrence for Q UICKSORT becomes T.n/D

T.n 1/C?.n/,which has the solution T.n/D?.n2/.

Solution to Exercise8.1-3

If the sort runs in linear time for m input permutations,then the height h of the

portion of the decision tree consisting of the m corresponding leaves and their

ancestors is linear.

Use the same argument as in the proof of Theorem8.1to show that this is impos-

sible for m D n?=2,n?=n,or n?=2n.

We have2h m,which gives us h lg m.For all the possible m’s given here,

lg m D .n lg n/,hence h D .n lg n/.

In particular,

n?

lg

D lg n? lg n n lg n n lg e lg n;

n

n?

lg

Solution to Exercise8.2-3

The following solution also answers Exercise8.2-2.

Notice that the correctness argument in the text does not depend on the order in

which A is processed.The algorithm is correct no matter what order is used!

But the modi?ed algorithm is not stable.As before,in the?nal for loop an element

equal to one taken from A earlier is placed before the earlier one(i.e.,at a lower

index position)in the output arrray B.The original algorithm was stable because

an element taken from A later started out with a lower index than one taken earlier.

But in the modi?ed algorithm,an element taken from A later started out with a

higher index than one taken earlier.

In particular,the algorithm still places the elements with value k in positions

C?k 1 C1through C?k ,but in the reverse order of their appearance in A.

8-2Selected Solutions for Chapter8:Sorting in Linear Time

Solution to Exercise8.3-4

Treat the numbers as3-digit numbers in radix n.Each digit ranges from0to n 1.

Sort these3-digit numbers with radix sort.

There are3calls to counting sort,each taking?.n C n/D?.n/time,so that the

total time is?.n/.

Selected Solutions for Chapter8:Sorting in Linear Time8-3 These n?leaves will each have probability1=n?,since each of the n?possible permutations is the input with the probability1=n?.Any remaining leaves will have probability0,since they are not reached for any input.

Without loss of generality,we can assume for the rest of this problem that paths leading only to0-probability leaves aren’t in the tree,since they cannot affect the running time of the sort.That is,we can assume that T A consists of only the n?leaves labeled1=n?and their ancestors.

b.If k>1,then the root of T is not a leaf.This implies that all of T’s leaves

are leaves in LT and RT.Since every leaf at depth h in LT or RT has depth

h C1in T,D.T/must be the sum of D.LT/,D.RT/,and k,the total number

of leaves.To prove this last assertion,let d T.x/D depth of node x in tree T.

Then,

D.T/D

X

x2leaves.T/

d T.x/

D

X

x2leaves.LT/d T.x/C

X

x2leaves.RT/

d T.x/

D

X

x2leaves.LT/.d LT.x/C1/C

X

x2leaves.RT/

.d RT.x/C1/

D

X

x2leaves.LT/d LT.x/C

X

x2leaves.RT/

d RT.x/C

X

x2leaves.T/

1

D D.LT/C D.RT/C k:

c.To show that

d.k/D min1 i k 1f d.i/C d.k i/C k g we will show sepa-

rately that

d.k/ min

1 i k 1

f d.i/C d.k i/C k g

and

d.k/ min

1 i k 1

f d.i/C d.k i/C k g:

To show that d.k/ min1 i k 1f d.i/C d.k i/C k g,we need only show that d.k/ d.i/C d.k i/C k,for i D1;2;:::;k 1.For any i from1 to k 1we can?nd trees RT with i leaves and LT with k i leaves such that D.RT/D d.i/and D.LT/D d.k i/.Construct T such that RT and LT are the right and left subtrees of T’s root respectively.Then

d.k/ D.T/(by de?nition of d as min D.T/value)

D D.RT/C D.LT/C k(by part(b))

D d.i/C d.k i/C k(by choice of RT and LT).

To show that d.k/ min1 i k 1f d.i/C d.k i/C k g,we need only show that d.k/ d.i/C d.k i/C k,for some i in f1;2;:::;k 1g.Take the tree T with k leaves such that D.T/D d.k/,let RT and LT be T’s right and left subtree,respecitvely,and let i be the number of leaves in RT.Then k i is the number of leaves in LT and

d.k/D D.T/(by choice of T)

D D.RT/C D.LT/C k(by part(b))

d.i/C d.k i/C k(by de?ntion of d as min D.T/value).

算法导论 第三版 第21章 答案 英

Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1

算法导论 第三版 第六章 答案 英

Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1

算法导论 第三版 第七章 答案 英

Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1

算法导论 第三版 第二章 答案 英

Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i]

算法导论 第三版 第24章 答案 英

Chapter24 Michelle Bodnar,Andrew Lohr April12,2016 Exercise24.1-1 If we change our source to z and use the same ordering of edges to decide what to relax,the d values after successive iterations of relaxation are: s t x y z ∞∞∞∞0 2∞7∞0 25790 25690 24690 Theπvalues are: s t x y z NIL NIL NIL NIL NIL z NIL z NIL NIL z x z s NIL z x y s NIL z x y s NIL Now,if we change the weight of edge(z,x)to4and rerun with s as the source,we have that the d values after successive iterations of relaxation are: s t x y z 0∞∞∞∞ 06∞7∞ 06472 02472 0247?2 Theπvalues are: s t x y z NIL NIL NIL NIL NIL NIL s NIL s NIL NIL s y s t NIL x y s t NIL x y s t 1

Note that these values are exactly the same as in the worked example.The di?erence that changing this edge will cause is that there is now a negative weight cycle,which will be detected when it considers the edge(z,x)in the for loop on line5.Since x.d=4>?2+4=z.d+w(z,x),it will return false on line7. Exercise24.1-2 Suppose there is a path from s to v.Then there must be a shortest such path of lengthδ(s,v).It must have?nite length since it contains at most|V|?1 edges and each edge has?nite length.By Lemma24.2,v.d=δ(s,v)<∞upon termination.On the other hand,suppose v.d<∞when BELLMAN-FORD ter-minates.Recall that v.d is monotonically decreasing throughout the algorithm, and RELAX will update v.d only if u.d+w(u,v)

《算法导论2版》课后答案_加强版2

1 算法导论第三次习题课 2008.12.17

2 19.1-1 如果x 是根节点：degree[sibling[x]] > sibling[x] 如果x 不是根节点：degree[sibling[x]] = sibling[x] –119.1-3 略

3 19.2-2 过程略( union 操作) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min ，用min-1代替-∞. [遍历堆中树的根节点]

4 15.1-1 15.1-2 略P195 或P329 15.1-4 f i [j]值只依赖f i [j-1]的值，从而可以从2n 压缩为2个。再加上f*、l*、l i [j]。 Print-station(l, I, j ) //i 为线路，j 为station if j>1 then Print-station(l, l i [j], j-1 ) print “line”I, “station”j;

5 15.2-1 略（见课本） 15.2-2 15.2-4 略 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j), j) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1,j) return MATRIX-MULTIPLY(x, y) else return A i

6 15.3-1 （归纳法）递归调用 枚举15.3-2 没有效果，没有重叠子问题 15.3-4 略 (3)n Ο3/2(4/) n n Θ

算法导论 第三版 第十九章 答案 英

Chapter19 Michelle Bodnar,Andrew Lohr April12,2016 Exercise19.2-1 First,we take the subtrees rooted at24,17,and23and add them to the root list.Then,we set H.min to18.Then,we run consolidate.First this has its degree2set to the subtree rooted at18.Then the degree1is the subtree rooted at38.Then,we get a repeated subtree of degree2when we consider the one rooted at24.So,we make it a subheap by placing the24node under18. Then,we consider the heap rooted at17.This is a repeat for heaps of degree1, so we place the heap rooted https://www.sodocs.net/doc/d09673049.html,stly we consider the heap rooted at23,and then we have that all the di?erent heaps have distinct degrees and are done,setting H.min to the smallest,that is,the one rooted at17. The three heaps that we end up with in our root list are: 23 17 38 30 41 and 1

算法导论参考 答案

第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort(T[] Input) where T:IComparable { T key; int i; for (int j = 1; j < Input.Length; j++) { key = Input[j]; i = j - 1; for (; i >= 0 && Input[i].CompareTo(key)>0;i-- ) Input[i + 1] = Input[i]; Input[i+1]=key; } } 揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j] 这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1. 如果按照大部分计算机编程语言的思路，修改为： INSERTION-SORT(A) 1 for j ← 1 to length[A] 2 do key ←A[j] 3 i ←j-1

Ch10算法导论 第三版 第十章 答案 英

Chapter10 Michelle Bodnar,Andrew Lohr April12,2016 Exercise10.1-1 4 41 413 41 418 41 Exercise10.1-2 We will call the stacks T and R.Initially,set T.top=0and R.top=n+1. Essentially,stack T uses the?rst part of the array and stack R uses the last part of the array.In stack T,the top is the rightmost element of T.In stack R, the top is the leftmost element of R. Algorithm1PUSH(S,x) 1:if S==T then 2:if T.top+1==R.top then 3:error“over?ow” 4:else 5:T.top=T.top+1 6:T[T.top]=x 7:end if 8:end if 9:if S==R then 10:if R.top?1==T.top then 11:error“over?ow” 12:else 13:R.top=R.top?1 14:T[T.top]=x 15:end if 16:end if 1

Algorithm2POP(S) if S==T then if T.top==0then error“under?ow” else T.top=T.top?1. return T[T.top+1] end if end if if S==R then if R.top==n+1then error“under?ow” else R.top=R.top+1. return R[R.top?1] end if end if Exercise10.1-3 4 41 413 13 138 38 Exercise10.1-4 Algorithm3ENQUEUE if Q.head==Q.tail+1,or Q.head==1and Q.tail==Q.length then error“over?ow” end if Q[Q.tail]=x if Q.tail==Q.length then Q.tail=1 else Q.tail=Q.head+1 end if Exercise10.1-5 As in the example code given in the section,we will neglect to check for over?ow and under?ow errors. 2

算法导论习题答案

Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort 重写为按非递减顺序排序 2.1.3 计算两个n 位的二进制数组之和 2.2 Analyzing algorithms 当前n-1个元素排好序后，第n 个元素已经是最大的元素了. 最好时间和最坏时间均为2()n Θ 2.3 Designing algorithms 2.3.3 计算递归方程的解 22()2(/2)2,1k if n T n T n n if n for k =?=?+ = >? （1） 当1k =时，2n =，显然有()lg T n n n = （2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===?， 则当1k i =+，即12i n +=时， 2.3.4 给出insertion sort 的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？ 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但

是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ 2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]≠x and i,()()b b n a n +=Θ 0a >时，()()2b b b b n a n n n +<+= 对于121,2b c c ==，12()b b b c n n a c n <+< 0a <时，()b b n a n +<

算法导论 第三版 第十六章 答案 英

Chapter16 Michelle Bodnar,Andrew Lohr April12,2016 Exercise16.1-1 The given algorithm would just stupidly compute the minimum of the O(n) numbers or return zero depending on the size of S ij.There are a possible number of subproblems that is O(n2)since we are selecting i and j so that 1≤i≤j≤n.So,the runtime would be O(n3). Exercise16.1-2 This becomes exactly the same as the original problem if we imagine time running in reverse,so it produces an optimal solution for essentially the same reasons.It is greedy because we make the best looking choice at each step. Exercise16.1-3 As a counterexample to the optimality of greedily selecting the shortest, suppose our activity times are{(1,9),(8,11),(10,20)}then,picking the shortest ?rst,we have to eliminate the other two,where if we picked the other two instead,we would have two tasks not one. As a counterexample to the optimality of greedily selecting the task that con?icts with the fewest remaining activities,suppose the activity times are {(?1,1),(2,5),(0,3),(0,3),(0,3),(4,7),(6,9),(8,11),(8,11),(8,11),(10,12)}.Then, by this greedy strategy,we would?rst pick(4,7)since it only has a two con- ?icts.However,doing so would mean that we would not be able to pick the only optimal solution of(?1,1),(2,5),(6,9),(10,12). As a counterexample to the optimality of greedily selecting the earliest start times,suppose our activity times are{(1,10),(2,3),(4,5)}.If we pick the ear-liest start time,we will only have a single activity,(1,10),whereas the optimal solution would be to pick the two other activities. Exercise16.1-4 Maintain a set of free(but already used)lecture halls F and currently busy lecture halls B.Sort the classes by start time.For each new start time which you encounter,remove a lecture hall from F,schedule the class in that room, 1

算法导论 第三版 第十七章 答案 英

Chapter17 Michelle Bodnar,Andrew Lohr April12,2016 Exercise17.1-1 It woudn’t because we could make an arbitrary sequence of MULT IP USH(k),MULT IP OP(k). The cost of each will beΘ(k),so the average runtime of each will beΘ(k)not O(1). Exercise17.1-2 Suppose the input is a1followed by k?1zeros.If we call DECREMENT we must change k entries.If we then call INCREMENT on this it reverses these k changes.Thus,by calling them alternately n times,the total time isΘ(nk). Exercise17.1-3 Note that this setup is similar to the dynamic tables discussed in section 17.4.Let n be arbitrary,and have the cost of operation i be c(i).Then, n i=1c(i)= lg(n) i=1 2i+ i≤n not a power of2 1≤ lg(n) i=1 2i+n=21+ lg(n) ?1+n≤4n?1+n≤5n∈O(n) So,since to?nd the average,we divide by n,the average runtime of each com-mand is O(1). Exercise17.2-1 To every stack operation,we charge twice.First we charge the actual cost of the stack operation.Second we charge the cost of copying an element later on.Since we have the size of the stack never exceed k,and there are always k operations between backups,we always overpay by at least enough.So,the ammortized cost of the operation is constant.So,the cost of the n operation is O(n). Exercise17.2-2 1

算法导论 第三版 第35章 答案 英

Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1

算法导论 课后题答案

Partial Solutions for Introduction to algorithms second edition Professor: Song You TA: Shao Wen

ACKNOWLEDGEMENT CLASS ONE: JINZI CLASS TWO: LIUHAO, SONGDINMIN, SUNBOSHAN, SUNYANG CLASS FOUR:DONGYANHAO, FANSHENGBO, LULU, XIAODONG, CLASS FIVE:GAOCHEN, WANGXIAOCHUAN, LIUZHENHUA, WANGJIAN, YINGYING CLASS SIX: ZHANGZHAOYU, XUXIAOPENG, PENGYUN, HOULAN CLASS: LIKANG,JIANGZHOU, ANONYMITY The collator of this Answer Set, SHAOWen, takes absolutely no responsibility for the contents. This is merely a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the solutions are wrong. If you have found an error, have a better solution or wish to contribute in some constructive way please send an Email to shao_wen_buaa@https://www.sodocs.net/doc/d09673049.html, It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Have fun with your algorithms and get a satisfactory result in this course. Best regards, SHAOWen