Review List for MidtermMidterm 1, 09/30/2013Analysis of AlgorithmsAsymptotic NotationsAsymptotic Notations--continuedSorting AlgorithmsSorting Lower BoundDivide and Conquer TechniqueSummationsGrowth of functionsBig O, , Master MethodMaster Method – Case 1Master Method – Case 2Master Method – Case 3Insertion SortInsertion Sort - ExampleInsertion Sort – Decision TreeQuick sortQuick Sort - PartitionQuick Sort - ExampleQuick Sort – Decision TreeRunning timeReview List for MidtermContents and Contents and RequirementsRequirementsMidterm 1, 09/30/2013•CLOSED BOOKCLOSED BOOK•What to bring:What to bring:–ASU IDASU ID–CalculatorCalculator•What NOT to bring:What NOT to bring:–Cell phone (should be turned off during exam)Cell phone (should be turned off during exam)–LaptopLaptop–Notes/BooksNotes/BooksAnalysis of Algorithms•What is an algorithm?What is an algorithm?•Computation model.Computation model.•Time complexity, space complexity.Time complexity, space complexity.•(Worse, average, best)-case analysis.(Worse, average, best)-case analysis.•Concentrate on concept:Concentrate on concept:–definitiondefinition–exampleexample–operations countoperations countAsymptotic Notations•O, O, , ,  notations: ( notations: (derivation and proofderivation and proof))–definitionsdefinitions–propertiesproperties–proofs (lectures)proofs (lectures)•Summations: (Summations: (derivation and proofderivation and proof))–geometric sequencegeometric sequence–arithmetic sequencearithmetic sequence–harmonic sequence (and others used in class)harmonic sequence (and others used in class)Asymptotic Notations--continued•Recurrences:Recurrences:–master method, three cases.master method, three cases.Sorting Algorithms•Insertion sortInsertion sort•QuicksortQuicksort•Algorithms and complexitiesAlgorithms and complexitiesSorting Lower Bound•Computing modelComputing model•Decision treesDecision trees•Lower boundLower bound•You need to know the results and be able You need to know the results and be able to draw the decision trees for 3 or 4 to draw the decision trees for 3 or 4 elements, or a root to leaf path for up to 7 elements, or a root to leaf path for up to 7 elements.elements.Divide and Conquer Technique•DivideDivide•ConquerConquer•CombineCombine•Examples:Examples:–QuicksortQuicksort–Searching a sorted arraySearching a sorted array–Block matrix multiplicationBlock matrix multiplicationSummations•1+2+3+ … + n = n(n+1) / 21+2+3+ … + n = n(n+1) / 2•1+1/2+1/3+1/4+…+1/n ~= log1+1/2+1/3+1/4+…+1/n ~= logeen = ln nn = ln n•1+1/2+1/4+1/8+…+(1/2)1+1/2+1/4+1/8+…+(1/2)nn = ? = ?•Sum Sum 00 n-1n-1xxii=(1-x=(1-xnn)/(1-x))/(1-x)•1+1/2+1/4+1/8+…+(1/2)1+1/2+1/4+1/8+…+(1/2)nn = (1-(1/2) = (1-(1/2)nn)/(1/2))/(1/2)•n->infinity => 2n->infinity => 2•1122+2+222+3+322+…+n+…+n2 2 = n(n+1)(2n+1)/6= n(n+1)(2n+1)/6Growth of functions•log (n)log (n)•sqrt(n)sqrt(n)•nn•n log(n)n log(n)•nn22•nn33•22nn•n!n!•nnnnBig O, , •If f(n) = nIf f(n) = n22 & g(n)=n & g(n)=n33–f(n) = O(g(n))f(n) = O(g(n))–g(n) = g(n) = (f(n))(f(n))•If f(n)= If f(n)= (g(n)) & f(n) = O(g(n))(g(n)) & f(n) = O(g(n))–f(n) = f(n) = (g(n))(g(n))Master Method•Recurrence must be of the formRecurrence must be of the formT(n) = aT(n/b) + f(n)T(n) = aT(n/b) + f(n)•Where a>=1 and b>1 and f(n) is an Where a>=1 and b>1 and f(n) is an asymptotically positive functionasymptotically positive function•Three CasesThree CasesMaster Method – Case 1•T(n) = 9T(n/3) + nT(n) = 9T(n/3) + n–a=9a=9–b=3b=3–log log bb a = log a = log 33 9 = 2 9 = 2–f(n) = O(n^((logf(n) = O(n^((logbba)-e)) for 0<e<=1a)-e)) for 0<e<=1–T(n)= T(n)= (n^(log(n^(logbba)) = a)) = (n(n22))Master Method – Case 2•T(n) = T(2n/3) + 1T(n) = T(2n/3) + 1–a=1a=1–b=3/2b=3/2–loglogbba=loga=log3/23/21=01=0–f(n) = f(n) = (n^(log(n^(logbba))a))–T(n) = T(n) = (n^(log(n^(logbba) lg n) = a) lg n) = (lg n)(lg n)Master Method – Case 3•T(n) = 3T(n/4)+ n lg nT(n) = 3T(n/4)+ n lg n–a = 3a = 3–b = 4b = 4–log log bb a = log a = log 44 3 ~= 0.793 3 ~= 0.793–f(n) = f(n) = (n^((log (n^((log bb a)+e)) a)+e)) •for 0<e<=(1-log43)~=0.217–Is af(n/b)<=cf(n) for c<1?Is af(n/b)<=cf(n) for c<1?•3*(n/4)*lg(n/4) <= c * n * lg n ? c=3/4 will work–T(n) = T(n) = (f(n)) = (f(n)) = (n lg n)(n lg n)Insertion SortInsertion-Sort(A)Insertion-Sort(A)11for j := 2 to length[A] dofor j := 2 to length[A] do22key := A[j]key := A[j]33// insert A[j] into sorted A[1..j-1]// insert A[j] into sorted A[1..j-1]44i := j -1i := j -155while i > 0 and A[i] > key dowhile i > 0 and A[i] > key do66A[i+1] := A[i]A[i+1] := A[i]77i := i - 1i := i - 188A[i+1] := keyA[i+1] := keyInsertion Sort - Example•Initial array: 7,2,5,3,6Initial array: 7,2,5,3,6–Key=2 => 2,7,5,3,6Key=2 => 2,7,5,3,6–Key=5 => 2,5,7,3,6Key=5 => 2,5,7,3,6–Key=3 => 2,3,5,7,6Key=3 => 2,3,5,7,6–Key=6 => 2,3,5,6,7Key=6 => 2,3,5,6,7Insertion Sort – Decision Tree•7,2,5,3,6 key=27,2,5,3,6 key=2•2,7,5,3,6 key=52,7,5,3,6 key=5•2,5,7,3,6 key=52,5,7,3,6 key=5•2,5,7,3,6 key=32,5,7,3,6 key=3•2,5,3,7,6 key=32,5,3,7,6 key=3•2,3,5,7,6 key=32,3,5,7,6 key=3•2,3,5,7,6 key=62,3,5,7,6 key=6•2,3,5,6,7 key=62,3,5,6,7 key=6Quick sortQuicksort (A, p,r)Quicksort (A, p,r)if p < r thenif p < r thenk := Partition(A, p, r)k := Partition(A, p, r)Quicksort (A, p, k-1)Quicksort (A, p, k-1)Quicksort (A, k+1, r)Quicksort (A, k+1, r)Quick Sort - PartitionPartition(A, p, r)Partition(A, p, r)1 x := A[r]1 x := A[r]2 i := p-12 i := p-13 for j:=p to r-1 do3 for j:=p to r-1 do4 If A[j] ≤ x then4 If A[j] ≤ x then5 i := i+15 i := i+16 exchange A[i] and A[j]6 exchange A[i] and A[j]7 exchange A[i+1] and A[r]7 exchange A[i+1] and A[r]8 return i+18 return i+1Quick Sort - Example•Initial array: 7,2,5,3,6Initial array: 7,2,5,3,6•Quicksort(A,1,5) => (7,2,5,3,6)Quicksort(A,1,5) => (7,2,5,3,6)•x=6 => 7,2,5,3,6 => 2,7,5,3,6 => 2,5,7,3,6 => x=6 => 7,2,5,3,6 => 2,7,5,3,6 => 2,5,7,3,6 => 2,5,3,7,6 => 2,5,3,6,72,5,3,7,6 => 2,5,3,6,7•Quicksort(A,1,3) => (2,5,3)Quicksort(A,1,3) => (2,5,3)•x=3 => 2,5,3 => 2,5,3 => 2,3,5 =>x=3 => 2,5,3 => 2,5,3 => 2,3,5 =>•Quicksort(A,1,1) => (2)Quicksort(A,1,1) => (2)•Quicksort(A,3,3) => (5)Quicksort(A,3,3) => (5)•Quicksort(A,5,5) =>