[PDF] Solutions for Introduction to algorithms second edition

View - Download Solutions for Introduction to algorithms second edition

Previous PDF

Next PDF

SolutionsforIntroductiontoalgorithms

secondedition

PhilipBille

funwithyouralgorithms.

Bestregards,

PhilipBille

Lastupdate:December9,2002

1:2-2

26n643(foundbyusingacalculator).

runningtime. 1-1

1111111

secondminutehourdaymonthyearcentury n3102391153244201373698169455661

2n19253136414956

n!9111213151718 2 2:1-2 nonincreasingorder. 2:1-3

Algorithm1LINEAR-SEARCH(A;v)

Input:A=ha1;a2;:::aniandavaluev.

Output:Anindexisuchthatv=A[i]ornilifv62A

fori 1tondo ifA[i]=vthen returni endif endfor returnnil 2:2-1 n

3=1000-100n2-100n+3=(n3).

2:2-2

Algorithm2SELECTION-SORT(A)

Input:A=ha1;a2;:::ani

Output:sortedA.

fori 1ton-1do j FIND-MIN(A;i;n)

A[j]$A[i]

endfor thenthelargest. nX i=1i! =(n2) 2:2-3 3 2:2-4 caseinputefciently. 2:3-5

Algorithm3BINARY-SEARCH(A;v;p;r)

Input:AsortedarrayAandavaluev.

Output:Anindexisuchthatv=A[i]ornil.

ifp>randv6=A[p]then returnnil endif j A[b(r-p)=2c] ifv=A[j]then returnj else ifvAlgorithm4CHECKSUMS(A;x)

Input:AnarrayAandavaluex.

A SORT(A)

n length[A] fori tondo returntrue endif endfor returnfalse 4 3:1-1 foralln>n0. 3:1-4 2 2 3-4 (1). aregreaterthanorequal1.Wehavethat: f(n)6cg(n))lgf(n)6lg(cg(n))=lgc+lgg(n)

Dividingbylgg(n)yields:

b=lg(c)+lgg(n) lgg(n)=lgclgg(n)+16lgc+1

Thelastinequalityholdssincelgg(n)>1.

f.Yes,f(n)=O(g(n))impliesg(n)=

1=cf(n)6g(n).

g.No,clearly2n66c2n=2=cp

2nforanyconstantcifnissufcientlylarge.

(f(n)). 5 4:1-1 clg(n-b).Assumethisholdsfordn=2e.Wehave:

T(n)6clg(dn=2-be)+1

6clg(n-b)

Thelastinequalityrequiresthatb>2andc>1.

4:2-1

T(n)=3T(bn=2c)+n

6n+(3=2)n+(3=2)2n++(3=2)lgn-1n+(nlg3)

=nlgn-1X i=0(3=2)i+(nlg3) =n(3=2)lgn-1 (3=2)-1+(nlg3) =2(n(3=2)lgn-n)+(nlg3) =2n3lgn

2lgn-2n+(nlg3)

=23lgn-2n+(nlg3) =2nlg3-2n+(nlg3) =(nlg3) obtain:

T(n)=3T(bn=2c)+n

63cbn=2clg3-cbn=2c+n

6

3cnlg3

2lg3-cn2+n

6cnlg3-cn

2+n

6cnlg3

Wherethelastinequalityholdsforc>2.

6 4:2-3

T(n)=4T(bn=2c)+cn

lgn-1X i=04 ibcn=2ic+(n2) 6 lgn-1X i=04 icn=2i+(n2) =cnlgn-1X i=02 i+(n2)+(n2) =cn2lgn-1

2-1+(n2)

=(n2)

T(n)=4T(bn=2c)+cn

64(cbn=2c2-cbn=2c)+cn

<4c(n=2)2-4cn=2+cn =cn2-2cn+cn =cn2-cn 4:3-1 n log24=n2

T(n)=4T(n=2)+n3.Sincen3=

(n2+)and4(n=2)3=1=2n36cn3forsomec<1we havethatT(n)=(n3). 7 6:1-1 notbelledwemayonlyhave2hvertices. 6:1-2 h6lgnMAX-HEAPIFY. 6:4-4 (nlgn).Thisisclearsincesortinghasa lowerboundof (nlgn) 6:5-3 theheapinthemax-heapimplementation. 6:5-4 thatHEAP-INCREASE-KEYdoesnotfail. 6:5-5

A[PARENT(i)].

8 6:5-7

Algorithm5HEAP-DELETE(A;i)

Input:Amax-heapAandintegersi.

A[i]$A[heap-size[A]]

heap-size[A] heap-size[A]-1 key A[i] ifkey6A[PARENT(i)]then

MAX-HEAPIFY(A;i)

else whilei>1andA[PARENT(i)]A[i]$A[PARENT(i)] i PARENT(i) endwhile endif 6:5-8 runningtimeisO(nlgk). 6-2

D-ARY-PARENT(i)

returnb(i-2)=d+1c

D-ARY-CHILD(i;j)

returnd(i-1)+j+1 9 theheightoftheheap,thatis(logdn). 10 7:1-2 alwayssatiedandithereforeisincrementedineachiteration.Sinceinitiallyi p-1andi+1 isreturnedthereturnedvalueisr-1. rithmtocheckforthiscaseexplicitly.quotesdbs_dbs10.pdfusesText_16

[PDF] design and analysis of algorithms stanford

[PDF] design procedure for combinational circuit

[PDF] design procedure for solid slab bridge

[PDF] design procedure of gravity retaining wall

[PDF] design procedure of helical gear

[PDF] design procedure of journal bearing

[PDF] design procedure of knuckle joint

[PDF] design procedure of spur gear

[PDF] design process architecture

[PDF] design process stages

[PDF] design standards accessible stations

[PDF] designated eld minutes california

[PDF] designer drapery hardware

[PDF] designer perfume recipes pdf

[PDF] despegar expedia investment