Math ReviewWhy do we need math in a data structures course?Examples – how much “time” does each of these algorithms take?Floors and CeilingsExponentsLogarithmsSlide 8Slide 9FactorialsModular ArithmeticSeriesSlide 13ProofsProof by InductionInductive Proof: ExampleExample (cont.)More Examples for Induction ProofsProof by CounterexampleAnother Example for a proof by CounterexampleProof by counterexampleProof by ContradictionExample for proof by contradictionProof by contradiction..Mathematical Recurrence vs. RecursionBasic Rules of RecursionSlide 27Slide 28Running time for Fibonacci(n)?Solving recurrencesSolving recurrences…Ponder thisRecursive Function CallsTail Recursion  IterationTower of HanoiTower of Hanoi: AlgorithmRecursive Algorithm for Tower of Hanoi (pseudocode)Tower of Hanoi: AnalysisSummaryTry it out yourself1Math ReviewCpt S 223. School of EECS, WSU2Why do we need math in a data structures course?To Analyze data structures and algorithmsDeriving formulae for time and memory requirementsWill the solution scale?Quantify the resultsProving algorithm correctnessCpt S 223. School of EECS, WSUExamples – how much “time” does each of these algorithms take? 3Algorithm1 (A,n) max = -infinity for (i=1 to n) {if(A[i]>max) max=A[i];}Output max;Cpt S 223. School of EECS, WSU T(n) = 2 T(n/2) + const.These are not a closed form yet. If you solve the recurrences, you will get,O(lg n) for Algorithm2, and O(n) for Algorithm3Algorithm2 (A, start, end) if (n<2) return mid = floor(n/2) if (condition#1) Algorithm2 (A,1,mid) else Algorithm2 (A,mid+1,n)Algorithm3 (A,n) if (n<2) return x = floor(n/2) Algorithm3 (A,1,x) Algorithm3 (A,x+1,n)// Assume A is an integer array of size nT(n)  n T(n)  T(n/2) + const.Definition: Let T(n) denote the time take by an algorithm on an input of size n.T(n)T(n/2)T(n/2)T(n)T(n/2)T(n/2)Floors and Ceilingsfloor(x), denoted , is the greatest integer ≤ xceiling(x), denoted , is the smallest integer ≥ xNormally used to divide input into integral parts5 x xNNN22Cpt S 223. School of EECS, WSUExponents6122222)(NNNNNNNABBABABABABAXXXXXXXXXXXXCpt S 223. School of EECS, WSULogarithms7logarithm" natural" ...7182.2;loglnloglg0 allfor loglogloglogloglog0,;logloglog1,0,,;logloglogX" base B of logarithm" log2eAAAAXXXABABABABABAABACBAABBBXABeBCCAAXPS: In Weiss book,log n  log2nOur convention for the course:lg n == log2 nlog n == log10 nln n == loge nCpt S 223. School of EECS, WSUWhat is the meaning of the log function?For example, lg 1024 8Cpt S 223. School of EECS, WSUExampleHow many times to halve an array of length n until its length is 1?9KeepHalving (n) i = 0 while n ≠ 1 i = i + 1 n = floor(n/2) return iWhat will be the value of i?Cpt S 223. School of EECS, WSUFactorials10ionapproximat sStirling' ))/1(1()/(n2n!!0 if )!1(0 if 1!nennnnnnnnnnn! == how many ways to order a set of n elements?Cpt S 223. School of EECS, WSUModular Arithmetic11 N) (mod BD AD andN) (mod CB CAThen )(mod If)10(mod16181 E.g.,N" modulo B tocongruent isA ")(mod)mod()mod(/modNBANBANBNANANANABasis of mostencryption schemes:(Message mod Key)Cpt S 223. School of EECS, WSU12SeriesGeneralLinearityArithmetic seriesNiNfffif0)(...)1()0()(NiNNi12)1(  NiNiNiigifcigicf00 0)()())()((Cpt S 223. School of EECS, WSU13SeriesGeometric seriesExampleHow many nodes in a complete binary tree of depth D?10 if ;11110001AAAAAAAiiNiiNiNi1522271910123Cpt S 223. School of EECS, WSU202122A=2, N=D=2(22+1-1) / (2-1)7ProofsWhat do we want to prove?Properties of a data structure always hold for all operationsAlgorithm’s running time / memory will never exceed some thresholdAlgorithm will always be correctAlgorithm will always terminateTechniquesProof by inductionProof by counterexampleProof by contradiction14Cpt S 223. School of EECS, WSU15Proof by InductionGoal: Prove some hypothesis is trueThree-step process1. Base case: Show hypothesis is true for some initial conditions2. Inductive hypothesis: Assume hypothesis is true for all values ≤ k3. Inductive step: Show hypothesis is true for next larger value (typically k+1)Variation:Ind/hyp: All values < k, Ind/step: show for value=kCpt S 223. School of EECS, WSUInductive Proof: ExampleProve arithmetic seriesBase case: Show true for N=116NiNNi12)1(112)11(11iiCpt S 223. School of EECS, WSU Base case verifiedExample (cont.)Ind/Hyp: Assume true for all N<=kInd/Step: Now see if it is true for N=k+1172)2)(1(2)1()1(22)1()1()1(111kkkkkkkkikikikiVariation: Assume hyp for N<k, and Check for N=kCpt S 223. School of EECS, WSUMore Examples for Induction ProofsProve the geometric seriesProve that the number of nodes N in a complete binary tree of depth D is 2D+1 -118NiNiAAA0111Cpt S 223. School of EECS, WSU19Proof by CounterexampleProve hypothesis is not true by giving an example that doesn’t workExample: 2N > N2 ? Proof: N=2 (or 3 or 4)Proof by example?Proof by lots of examples?Proof by all possible examples?Empirical proofHard when input size and contents can vary arbitrarilyCpt S 223. School of EECS, WSUAnother Example for a proof by CounterexampleGiven N cities and costs for traveling between each pair of cities, a “least-cost tour” is one which visits every city exactly once with the least costHypothesis: Any sub-path within any least-cost tour will also be a least-cost tour for those cities included in the sub-path.20Is this hypothesis true?Cpt S 223. School of EECS, WSU…sub-path also least-costLeast-cost tourProof by counterexampleCounterexampleCost (ABCD) = 40 (optimal)Cost (ABC) = 30Cost (ACB) = 2021AD CB20101010010010Least cost tour for {A,B,C}Not the least cost tour for {A,B,C}Conclusion: Least cost tours don’t necessarily contain smaller least cost toursCpt S 223. School of EECS, WSUProof by Contradiction1. Start by assuming that the hypothesis is false2. Show this assumption could lead to a contradiction (i.e.,