Cpt S 223, Fall 2007 Copyright: Washington State University 1Mathematical ReviewCpt S 223, Fall 2007 Copyright: Washington State University 2Review Topics• Series & summations (see WebCThandout)• Proof• Recursion• Pseudocodes• Reading: Weiss, Chapter 1 and 2Cpt S 223, Fall 2007 Copyright: Washington State University 3Series Evaluation Techniques• Sum of an infinite geometric series with 0<x<1?• Sum of first n numbers?Cpt S 223, Fall 2007 Copyright: Washington State University 4Different Techniques to Write Proofs• By induction– Confirm theorem for a base case– Inductive hypothesis: Assume true for some arbitrary step, i– Show that the theorem holds for the next step, typically i+1• Eg., – Claim: Any Fibonacci number Fisatisfies Fi<(5/3)ifor all i>=1– Remember: There is no such thing called “proof by example”for universal claims like the above!Cpt S 223, Fall 2007 Copyright: Washington State University 5Proof Techniques…• By Counterexample– Eg., prove that the claim Fi<=i2is false• Case i=11 • By Contradiction– CLAIM: “IF a THEN b”– Technique: First assume “IF a THEN NOT b” and then arrive at a contradiction – Eg., prove that there are infinite number of primesCpt S 223, Fall 2007 Copyright: Washington State University 6Proof Techniques…• Proof by Contrapositive– “IF a THEN b” is equivalent to “IF NOT b THEN NOT a”– So instead of proving “IF a THEN b” (the forward claim), prove “IF NOT b THEN NOT a” (the contrapositive claim)– Eg., Claim: IF x+y is even, THEN parity(x)=parity(y)– Proof: • Prove the following contrapositive claim: – IF parity(x)≠parity(y) THEN x+y is odd• The above claim is easier to prove (just consider all possible cases and we are done)Cpt S 223, Fall 2007 Copyright: Washington State University 7Some Logical Equivalences• “a IF AND ONLY IF b”= “IF a THEN b” AND “IF b THEN a”– Useful in bi-directional proofs– Sometimes abbreviated as “IFF”• “a ONLY IF b” = “IF a THEN b”• “IF a THEN b” = “IF NOT b THEN NOT a”Cpt S 223, Fall 2007 Copyright: Washington State University 8Logarthims• log(n) = log10(n)• lg(n) = log2(n)• ln(n) = loge(n)• log a + log b = log ab• log ax= x log a• log (log (log n))) = log log log n• log * n =log log log …. n – Meaning: How many times you need to divide n by the base before getting a quotient of 1?Cpt S 223, Fall 2007 Copyright: Washington State University 9Recursion• Base case• Termination• Recursive stack• Tail recursion should be avoided• Eg., recursive function: • f(x)=2f(x-1)+x2Can be easily changed to a while loop!Also, what happens if x<0?Cpt S 223, Fall 2007 Copyright: Washington State University 10Recursive Function CallsMA A B CBBD EEFMA A BBBCD EF EtimeCall sequenceCpt S 223, Fall 2007 Copyright: Washington State University 11Tail Recursion IterationMAAAMA A AIterationTail recursiontimeCpt S 223, Fall 2007 Copyright: Washington State University 12Example Applications• Towers of Hanoi• Tree traversals• Binary searchCpt S 223, Fall 2007 Copyright: Washington State University 13Tower of HanoiGoal: Move all disks from peg A to peg C using peg BRule: Larger disks cannot be placed above smaller disksInvented by a French Mathematician Edouard Lucas, 1883ACBQuestion: What is the minimum number of moves necessary to solve the problem?Cpt S 223, Fall 2007 Copyright: Washington State University 14Tower of Hanoi…• Let T(n)= minimum number of moves required to solve the problem• A Recursive Algorithm:1. First, move the top n-1 disks, “recursively”, from A to B2. Move disk n (ie., largest & bottom-most in A) from A to C3. Then, move all the n-1 disks, “recursively”, from B to C through A• Analysis:– T(0)=0 Base case– T(n) = 2.T(n-1)+1 recurrence• Solving this yields T(n)=2n-1• In the original Tower of Hanoi problem, n=8 & so fine!• For Tower of Brahma, n=64⇒ 264-1 moves⇒ Assuming each move takes 1 microsecond, this would take 5,000 centuries to complete⇒ So lots of time before the world ends!Cpt S 223, Fall 2007 Copyright: Washington State University 15Recursive Algorithm for Tower of Hanoi• Move (n: disk, A, B, C)• PRE: n disks on A; B and C unaffected• POST: n disks on B; A and C unaffected• BEGIN– IF n=0 THEN RETURN– Move (n-1, A,C,B)– Move nthdisk from A to B directly– Move (n-1,C,B,A) •
View Full Document
Unlocking...