Daa Summary

  • Published on
    13-Oct-2015

  • View
    4

  • Download
    0

Embed Size (px)

DESCRIPTION

Design and Analysis of Algorithms

Transcript

<ul><li><p>20/11/2013</p><p>1</p><p>DAASummaryCSE3rd YearGCET</p><p>Syllabus</p><p> UnitI:Introduction:Algorithms,Analyzingalgorithms Complexity of algorithms Growth ofalgorithms,Complexityofalgorithms,Growthoffunctions,Performancemeasurements,SortingandorderStatistics Shellsort,Quicksort,Mergesort,Heapsort,Comparisonofsortingalgorithms,Sortinginlineartime.</p><p> UnitII:AdvancedDataStructures:RedBlacktrees,B trees,BinomialHeaps,FibonacciHeaps.</p><p>11Nov2013 2DAA(ECS502)</p></li><li><p>20/11/2013</p><p>2</p><p>Syllabus Unit III:DivideandConquerwithexamplessuchasSorting,MatrixMultiplication,ConvexhullandSearching Greedy methods with examples such asSearching.GreedymethodswithexamplessuchasOptimalReliabilityAllocation,Knapsack,MinimumSpanningtrees PrimsandKruskals algorithms,Singlesourceshortestpaths Dijkstras andBellmanFordalgorithms.</p><p> Unit IV:DynamicprogrammingwithexamplessuchK k All i h t t th W h l dasKanpsack,Allpairshortestpaths Warshals and</p><p>Floydsalgorithms,Resourceallocationproblem.Backtracking,BranchandBoundwithexamplessuchasTravellingSalesmanProblem, GraphColoring, nQueenProblem, HamiltonianCyclesandSumofsubsets.</p><p>11Nov2013 3DAA(ECS502)</p><p>Syllabus</p><p> UnitV:SelectedTopics:AlgebraicComputation, FastFourierTransform, StringMatching, TheoryofNPcompleteness,ApproximationalgorithmsandRandomizedalgorithms.</p><p>References:1. ThomasH.Coreman,CharlesE.Leiserson andRonaldL.Rivest,</p><p>IntroductiontoAlgorithms,Printice HallofIndia.2. RCT Lee, SS Tseng, RC Chang and YT Tsai, Introduction to the Design2. RCTLee,SSTseng,RCChangandYTTsai, IntroductiontotheDesign</p><p>andAnalysisofAlgorithms,McGraw Hill,2005.3. E.Horowitz&amp;SSahni,"FundamentalsofComputerAlgorithms",4. Aho,Hopcraft,Ullman,TheDesignandAnalysisofComputer</p><p>AlgorithmsPearson</p><p>11Nov2013 4DAA(ECS502)</p></li><li><p>20/11/2013</p><p>3</p><p>INSERTIONSORTAlg.: INSERTIONSORT(A)forj 2 ton a8a7a6a5a4a3a2a1</p><p>1 2 3 4 5 6 7 8</p><p>dokeyA[ j ]InsertA[ j ] intothesortedsequenceA[1 . . j -1]i j - 1whilei &gt; 0 andA[i] &gt; key</p><p>d A[i 1] A[i]</p><p>key</p><p>5</p><p>doA[i + 1] A[i]i i 1</p><p>A[i + 1] key Insertionsort sortstheelementsinplace</p><p>MergeSortAlg.: MERGESORT(A, p, r)</p><p>1 2 3 4 5 6 7 8</p><p>62317425</p><p>p rq</p><p>ifp &lt; r Checkforbasecasethenq (p + r)/2 Divide</p><p>MERGESORT(A, p, q) ConquerMERGESORT(A, q + 1, r) Conquer</p><p>(A )</p><p>6</p><p>MERGE(A, p, q, r) Combine</p><p> Initialcall: MERGESORT(A, 1, n)</p></li><li><p>20/11/2013</p><p>4</p><p>Merge PseudocodeAlg.: MERGE(A,p,q,r)1. Computen1 and n2</p><p>1 2 3 4 5 6 7 8</p><p>63217542</p><p>p rq</p><p>2. Copythefirstn1 elementsinto L[1 . . n1 + 1] andthenextn2 elementsintoR[1 . . n2 + 1]</p><p>3. L[n1 + 1] ; R[n2 + 1] 4. i 1; j 15. fork p tor6 do if L[ i ] R[ j ]</p><p>p q</p><p>7542</p><p>6321rq+1</p><p>L</p><p>R</p><p>n1 n2</p><p>7</p><p>6. doifL[ i ] R[ j ]7. thenA[k] L[ i ]8. i i + 19. elseA[k] R[ j ]10. j j + 1</p><p>RandomizedQuicksortAlg. : RANDOMIZEDQUICKSORT(A, p, r)</p><p>ifp &lt; r</p><p>thenq RANDOMIZEDPARTITION(A, p, r)</p><p>(A )</p><p>8</p><p>RANDOMIZEDQUICKSORT(A, p, q)</p><p>RANDOMIZEDQUICKSORT(A, q + 1, r)</p></li><li><p>20/11/2013</p><p>5</p><p>RandomizedPARTITION</p><p>Alg.: RANDOMIZEDPARTITION(A, p, r)</p><p>i RANDOM(p, r)</p><p>exchange A[p] A[i]</p><p>9</p><p>exchangeA[p] A[i]</p><p>returnPARTITION(A, p, r)</p><p>PARTITIONAlg.:PARTITION(A,p,r)</p><p>x A[r]i p - 1</p><p>A[pi] x A[i+1j-1] &gt; xp i i+1 rj1 ji p 1</p><p>forj p tor - 1doifA[ j ] x</p><p>theni i + 1exchangeA[i]A[j]</p><p>exchangeA[i + 1]A[r]</p><p>unknown</p><p>pivot</p><p>10</p><p>returni + 1ChoosesthelastelementofthearrayasapivotGrowsasubarray [p..i]ofelementsxGrowsasubarray [i+1..j1]ofelements&gt;xRunningTime:(n),wheren=rp+1</p></li><li><p>20/11/2013</p><p>6</p><p>Alg: HEAPSORT(A)</p><p>1. BUILDMAXHEAP(A) O(n)2. fori length[A] downto23. doexchangeA[1] A[i]4. MAXHEAPIFY(A, 1, i - 1)</p><p>( )</p><p>O(lgn)</p><p>n-1 times</p><p>11</p><p> Runningtime:O(nlgn) --- Can be shown to be (nlgn)</p><p>BuildingaHeap ConvertanarrayA[1 n] intoamaxheap(n = length[A]) TheelementsinthesubarrayA[(n/2+1) .. n] areleaves</p><p>Alg: BUILDMAXHEAP(A)1. n =length[A]2. for i n/2 downto 1</p><p> ApplyMAXHEAPIFYonelementsbetween1 andn/2</p><p>1</p><p>4</p><p>3</p><p>1</p><p>2 3</p><p>12</p><p>3. doMAXHEAPIFY(A, i, n) 214 8</p><p>16</p><p>7</p><p>9 104 5 6 7</p><p>8 9 10</p><p>4 1 3 2 16 9 10 14 8 7A:</p></li><li><p>20/11/2013</p><p>7</p><p>MaintainingtheHeapProperty Assumptions: LeftandRight</p><p>bt f i</p><p>Alg: MAXHEAPIFY(A, i, n)1. lLEFT(i)2 RIGHT(i)subtrees ofi</p><p>aremaxheaps A[i] maybe</p><p>smallerthanitschildren</p><p>2. rRIGHT(i)3. if l n andA[l] &gt; A[i]4. then largest l5. else largest i6. if r n andA[r] &gt; A[largest]7 then largest r</p><p>13</p><p>7. then largest r8. if largest i9. then exchangeA[i] A[largest]10. MAXHEAPIFY(A, largest, n)</p><p>AnalysisofCountingSortAlg.: COUNTINGSORT(A,B,n,k)1. fori 0 tor2 do C[ i ] 0 (r)2. doC[ i ] 03. forj 1 ton4. doC[A[ j ]] C[A[ j ]] + 15. C[i] containsthenumberofelementsequaltoi6. fori 1 tor7. doC[ i ] C[ i ] + C[i -1]</p><p>(n)</p><p>(r)</p><p>14</p><p>[ ] [ ] [ ]8. C[i] containsthenumberofelements i9. forj n downto 110. doB[C[A[ j ]]] A[ j ]11. C[A[ j ]] C[A[ j ]] - 1</p><p>(n)</p><p>Overalltime:(n + r)</p></li><li><p>20/11/2013</p><p>8</p><p>AnalysisofBucketSortAlg.: BUCKETSORT(A,n)</p><p>for i 1 to nfori 1 tondoinsertA[i]intolistB[nA[i]]</p><p>fori 0 ton - 1dosortlistB[i] withquicksortsort</p><p>B[0] B[1] B[ 1]</p><p>O(n)</p><p>(n)</p><p>15</p><p>concatenatelistsB[0], B[1], . . . , B[n -1]togetherinorderreturntheconcatenatedlists</p><p>O(n)</p><p>(n)</p><p>RBINSERT(T, z)1. y NIL Initializenodesxandy</p><p>Th h t th l ith i t</p><p>26</p><p>17 41</p><p>30 47</p><p>38 50</p><p>2. x root[T]3. whilex NIL4. doy x5. ifkey[z] &lt; key[x]</p><p> Throughoutthealgorithmypointstotheparentofx</p><p> Godownthetreeuntilreachingaleaf Atthatpointyisthe</p><p>16</p><p>6. thenx left[x]7. elsex right[x]8. p[z] y</p><p>p yparentofthenodetobeinserted</p><p> Setstheparentofztobey</p></li><li><p>20/11/2013</p><p>9</p><p>RBINSERT(T, z)9. ify = NIL10. thenroot[T] z Thetreewasempty:setthenewnodetobetheroot</p><p>26</p><p>17 41</p><p>30 47</p><p>38 50</p><p>11. elseifkey[z] &lt; key[y]12. thenleft[y] z13. elseright[y] z14. left[z] NIL</p><p>Otherwise,setztobetheleftorrightchildofy,dependingonwhethertheinsertednodeissmallerorlargerthanyskey</p><p>17</p><p>15. right[z] NIL16. color[z] RED17. RBINSERTFIXUP(T, z)</p><p>Setthefieldsofthenewlyaddednode</p><p>Fixanyinconsistenciesthatcouldhavebeenintroducedbyaddingthisnewrednode</p><p>RBINSERTFIXUP(T, z)1. whilecolor[p[z]] =RED2. doifp[z] = left[p[p[z]]]</p><p> i h [ [ [ ]]]</p><p>Thewhilelooprepeatsonlywhencase1isexecuted:O(lgn) times</p><p>Set the value of xs uncle3. theny right[p[p[z]]]4. ifcolor[y] = RED5. thenCase16. elseifz = right[p[z]]7. thenCase2</p><p>Setthevalueofx s uncle</p><p>18</p><p>8. Case39. else(sameasthenclausewithright</p><p>andleftexchanged)10. color[root[T]] BLACK Wejustinsertedtheroot,or</p><p>Theredviolationreachedtheroot</p></li><li><p>20/11/2013</p><p>10</p><p>LEFTROTATE(T,x)1. y right[x] Sety2. right[x] left[y] ysleftsubtreebecomesxsrightsubtree3 if left[y] NIL3. ifleft[y] NIL4. thenp[left[y]] x Settheparentrelationfromleft[y]tox5. p[y] p[x] Theparentofxbecomestheparentofy6. ifp[x] = NIL7. thenroot[T] y8 else if x = left[p[x]]</p><p>19</p><p>8. elseifx = left[p[x]]9. thenleft[p[x]] y10. elseright[p[x]] y11. left[y] x Putxonysleft12. p[x] y ybecomesxsparent</p><p>PRIM(V, E, w, r)1. Q 2. foreachu V3. dokey[u] O(V) ifQisimplementedas</p><p>Totaltime:O(VlgV + ElgV) = O(ElgV)</p><p>y[ ]4. [u]NIL5. INSERT(Q, u)6. DECREASEKEY(Q, r, 0) key[r] 07. whileQ 8. douEXTRACTMIN(Q)</p><p>aminheap</p><p>Executed|V|timesTakesO(lgV)</p><p>Minheapoperations:O(VlgV)</p><p>O(lgV)</p><p>20</p><p>9. foreachv Adj[u]10. doifv Q andw(u, v) &lt; key[v]11. then[v] u12. DECREASEKEY(Q, v, w(u, v))</p><p>ExecutedO(E)timestotalConstant</p><p>TakesO(lgV)O(ElgV)</p></li><li><p>20/11/2013</p><p>11</p><p>UsingFibonacciHeaps Dependingontheheapimplementation,runningtimecould be improved!couldbeimproved!</p><p>21</p><p>1. A2. foreachvertexv V3. doMAKESET(v)</p><p>KRUSKAL(V, E, w)</p><p>O(V)3. doMAKE SET(v)4. sortEintonondecreasingorderbyw5. foreach(u, v) takenfromthesortedlist6. doifFINDSET(u) FINDSET(v)7. thenAA {(u, v)}8. UNION(u v)</p><p>O(ElgE)</p><p>O(E)</p><p>O(lgV)</p><p>22</p><p>8. UNION(u, v)9. returnARunningtime:O(V+ElgE+ElgV)=O(ElgE) dependentonthe</p><p>implementationofthedisjointsetdatastructure Runningtime:O(V+ElgE+ElgV)=O(ElgE) SinceE=O(V2),wehavelgE=O(2lgV)=O(lgV)</p><p>O(lgV)</p><p>O(ElgV)</p></li><li><p>20/11/2013</p><p>12</p><p>BELLMANFORD(V, E, w, s)1. INITIALIZESINGLESOURCE(V,s)2. fori1to|V| 1</p><p>(V)O(V)</p><p>O(VE)3. doforeachedge(u,v) E4. doRELAX(u,v,w)5. foreachedge(u,v) E6. doifd[v]&gt;d[u]+w(u,v)7. then return FALSE</p><p>O(E)</p><p>O(E)</p><p>O(VE)</p><p>23</p><p>7. thenreturnFALSE8. returnTRUE</p><p>Runningtime:O(V+VE+E)=O(VE)</p><p>RelaxationStep Relaxinganedge(u,v)=testingwhetherwecan</p><p>improvetheshortestpathtovfoundsofarbygoingthroughu</p><p>d[ ] d[ ] ( ) Ifd[v] &gt; d[u] + w(u, v) wecanimprovetheshortestpathtov d[v]=d[u]+w(u,v)[v] u</p><p>2u v</p><p>2u v</p><p>Afterrelaxation:d[v] d[u] + w(u, v)s s</p><p>24</p><p>5 9</p><p>5 72</p><p>u v</p><p>RELAX(u,v,w)</p><p>5 6</p><p>5 62</p><p>u v</p><p>RELAX(u,v,w)</p><p>nochange</p></li><li><p>20/11/2013</p><p>13</p><p>Dijkstra(G,w,s)1. INITIALIZESINGLESOURCE(V, s)2. S3 Q V[G]</p><p>(V)</p><p>O(V) build min heap3. QV[G]4. whileQ 5. do uEXTRACTMIN(Q)6. SS {u}7. foreachvertexv Adj[u]</p><p>O(V)buildminheapExecutedO(V)times</p><p>O(lgV)</p><p>O(E)times</p><p>O(VlgV)</p><p>25</p><p>j8. doRELAX(u, v, w)9. UpdateQ(DECREASE_KEY)</p><p>Runningtime:O(VlgV + ElgV) = O(ElgV)</p><p>( )(total)</p><p>O(lgV)</p><p>O(ElgV)</p><p>Floyd'sAlgorithm:Using2Dmatrices</p><p>Floyd1.DW//initializeD arraytoW[]2.P 0//initializeParrayto[0]3.fork 1ton</p><p>//ComputingDfromD4.dofori 1ton5.doforj 1ton6. if(D[i,j ]&gt;D[i,k ]+ D[k,j ])7 th D[ i j ] D[ i k ] D[ k j ]</p><p>FloydsAlgorithm26</p><p>7. thenD[i,j ] D[i,k ]+ D[k,j ]8. P[i,j ] k;9. elseD[i,j ] D[i,j ]10.MoveDtoD.</p></li><li><p>20/11/2013</p><p>14</p><p>Printingintermediatenodesonshortestpathfromqtor</p><p>path(index q,r)if (P[q,r]0)</p><p>h( P[ ]) 30 0</p><p>1 2 3</p><p>1path(q,P[q,r])println(v+P[q,r])path(P[q,r],r)return;</p><p>//nointermediatenodeselse return</p><p>BeforecallingpathcheckD[q,r]</p></li><li><p>20/11/2013</p><p>15</p><p>rightDiagonal[row-col]=!available;if (row&lt; squares-1)</p><p>tQ ( +1)putQueen(row+1);else</p><p>print(" solution found);column[col]=available;leftDiagonal[row+col]=available;rightDiagonal[row-col]= available;</p><p>}}} </p><p>Navestringmatching</p><p>Runningtime:O((nm+1)m).</p></li><li><p>20/11/2013</p><p>16</p><p>Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.</p><p>Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.</p></li><li><p>20/11/2013</p><p>17</p><p>11Nov2013 DAA(ECS502) 33</p><p>11Nov2013 DAA(ECS502) 34</p></li></ul>