Slide 1AnnouncementsTodayMathematical inductionExamplePowers of 2Therefore…Logarithms and ExponentsLogarithms and ExponentsLogarithms and ExponentsLogarithms and ExponentsProperties of logarithmsLog base doesn’t matter much!Algorithm AnalysisExampleExampleExampleExampleLower-order terms don’t matterRecurrence EquationsBig-O: Common NamesCSE332: Data AbstractionsLecture 2: Math Review; Algorithm AnalysisDan GrossmanSpring 2010AnnouncementsProject 1 posted–Section materials on using Eclipse will be very useful if you have never used it–(Could also start in a different environment if necessary)–Section material on generics will be very useful for Phase BHomework 1 postedFeedback on typos is welcome–Won’t announce every time I update posted materials with minor fixesSpring 2010 2CSE332: Data AbstractionsToday•Finish discussing queues•Review math essential to algorithm analysis–Proof by induction–Powers of 2–Exponents and logarithms•Begin analyzing algorithms–Using asymptotic analysis (continue next time)Spring 2010 3CSE332: Data AbstractionsMathematical inductionSuppose P(n) is some predicate (mentioning integer n)–Example: n ≥ n/2 + 1To prove P(n) for all integers n ≥ c, it suffices to prove1. P(c) – called the “basis” or “base case”2. If P(k) then P(k+1) – called the “induction step” or “inductive case”Why we will care: To show an algorithm is correct or has a certain running time no matter how big a data structure or input value is(Our “n” will be the data structure or input size.)Spring 2010 4CSE332: Data AbstractionsExampleP(n) = “the sum of the first n powers of 2 (starting at 0) is 2n-1”Theorem: P(n) holds for all n ≥ 1Proof: By induction on n•Base case: n=1. Sum of first 1 power of 2 is 20 , which equals 1. And for n=1, 2n-1 equals 1.•Inductive case:–Assume the sum of the first k powers of 2 is 2k-1–Show the sum of the first (k+1) powers of 2 is 2k+1-1Using assumption, sum of the first (k+1) powers of 2 is(2k-1) + 2(k+1)-1 = (2k-1) + 2k = 2k+1-1Spring 2010 5CSE332: Data AbstractionsPowers of 2•A bit is 0 or 1•A sequence of n bits can represent 2n distinct things–For example, the numbers 0 through 2n-1•210 is 1024 (“about a thousand”, kilo in CSE speak)•220 is “about a million”, mega in CSE speak•230 is “about a billion”, giga in CSE speakJava: an int is 32 bits and signed, so “max int” is “about 2 billion” a long is 64 bits and signed, so “max long” is 263-1Spring 2010 6CSE332: Data AbstractionsTherefore…Could give a unique id to…•Every person in the U.S. with 29 bits•Every person in the world with 33 bits•Every person to have ever lived with 38 bits (estimate)•Every atom in the universe with 250-300 bitsSo if a password is 128 bits long and randomly generated, do you think you could guess it? Spring 2010 7CSE332: Data AbstractionsLogarithms and Exponents•Since so much is binary in CS log almost always means log2 •Definition: log2 x = y if x = 2y•So, log2 1,000,000 = “a little under 20”•Just as exponents grow very quickly, logarithms grow very slowlySpring 2010 8CSE332: Data AbstractionsSee Excel filefor plot data –play with it!Logarithms and Exponents•Since so much is binary log in CS almost always means log2 •Definition: log2 x = y if x = 2y•So, log2 1,000,000 = “a little under 20”•Just as exponents grow very quickly, logarithms grow very slowlySpring 2010 9CSE332: Data AbstractionsSee Excel filefor plot data –play with it!Logarithms and Exponents•Since so much is binary log in CS almost always means log2 •Definition: log2 x = y if x = 2y•So, log2 1,000,000 = “a little under 20”•Just as exponents grow very quickly, logarithms grow very slowlySpring 2010 10CSE332: Data AbstractionsSee Excel filefor plot data –play with it!Logarithms and Exponents•Since so much is binary log in CS almost always means log2 •Definition: log2 x = y if x = 2y•So, log2 1,000,000 = “a little under 20”•Just as exponents grow very quickly, logarithms grow very slowlySpring 2010 11CSE332: Data AbstractionsSee Excel filefor plot data –play with it!Properties of logarithms•log(A*B) = log A + log B–So log(Nk)= k log N•log(A/B) = log A – log B•log(log x) is written log log x–Grows as slowly as 22 grows fast•(log x)(log x) is written log2x–It is greater than log x for all x > 2Spring 2010 12CSE332: Data AbstractionsyLog base doesn’t matter much!“Any base B log is equivalent to base 2 log within a constant factor”–And we are about to stop worrying about constant factors!–In particular, log2 x = 3.22 log10 x–In general, logB x = (logA x) / (logA B) Spring 2010 13CSE332: Data AbstractionsAlgorithm AnalysisAs the “size” of an algorithm’s input grows (integer, length of array, size of queue, etc.):–How much longer does the algorithm take (time)–How much more memory does the algorithm need (space)Because the curves we saw are so different, we often only care about “which curve we are like”Separate issue: Algorithm correctness – does it produce the right answer for all inputs–Usually more important, naturallySpring 2010 14CSE332: Data AbstractionsExample•What does this pseudocode return? x := 0; for i=1 to N do for j=1 to i do x := x + 3; return x;•Correctness: For any N ≥ 0, it returns…Spring 2010 15CSE332: Data AbstractionsExample•What does this pseudocode return? x := 0; for i=1 to N do for j=1 to i do x := x + 3; return x;•Correctness: For any N ≥ 0, it returns 3N(N+1)/2•Proof: By induction on n–P(n) = after outer for-loop executes n times, x holds 3n(n+1)/2–Base: n=0, returns 0–Inductive: From P(k), x holds 3k(k+1)/2 after k iterations. Next iteration adds 3(k+1), for total of 3k(k+1)/2 + 3(k+1) = (3k(k+1) + 6(k+1))/2 = (k+1)(3k+6)/2 = 3(k+1)(k+2)/2Spring 2010 16CSE332: Data AbstractionsExample•How long does this pseudocode run? x := 0; for i=1 to N do for j=1 to i do x := x + 3; return x;•Running time: For any N ≥ 0, –Assignments, additions, returns take “1 unit time”–Loops take the sum of the time for their iterations•So: 2 + 2*(number of times inner loop runs)–And how many times is that…Spring 2010 17CSE332: Data AbstractionsExample•How long does this pseudocode run? x := 0; for i=1 to N do for j=1 to i do