CS211 Spring 2002 Lecture 4: OOP Overview 1/30/2003 ------------------------------------------------------------------------------- 0) Announcements: + Just added? See http://www.cs.cornell.edu/courses/cs211/2003sp/ Read syllabus! Do everything in "What To Do First"!!! + A2 posted soon (Thurs night/Fri) Objectives/Topics of Lecture 4: + wrapup of L3 (trees) + induction + intro to recursion (maybe starts on Tues) Credits + I'm borrowing massively from KP's CS211 notes, the course texts, a few handbooks, and various on-line notes, including my own :-) ------------------------------------------------------------------------------- 1) Motivating Induction and Recursion Want a method to determine how many ways to arrange n distinct objects.... (permutations)....call method "myFact(n)" + if n = 1, there are ___________ ways, so myFact(1) = _______ + if n > 1, # of ways = ? - block example for 2, 3, .... - myFact(n) = __________________ for _________ + General convention of myFact(n) is really _____________ where factorial(n) = ____________________ factorial(0) = ____ operator notation: _______ + the factorial method: // Precondition: n is a nonneg integer // Postcondition: n! is generated and returned public int factorial(int n ) { if ( ________ ) return ________ ; else return ____________________________________ } // Method factorial + how do you know that this works??? ------------------------------------------------------------------------------- 2) Recursive Definitions from (1): f(0) = 1 f(n) = n*f(n-1) for all n > 0 also, f(n) = 1*_________________ how do we know the defs are the same? new example: let N be set of all natural numbers (nonneg integers): N = { __________ } let S(n) be a function where S(n) = sum of nat nums from 0 to n, incl. how to express S(n)? (a) iterative form: (b) closed form: how do we know (a)=(b)? (besides using some principles of series) "weirder" example: For all integers n >= 8, n cents postage can be made using only 3-cent and 5-cent stamps. Uh oh..... ------------------------------------------------------------------------------- 3) The Domino Principle (courtesy of a lot of people, but with DIS-twist in lecture :-) Scenario: + n equally spaced dominos with space < domino length: + how to prove that all dominos fall if you tip over the first one? Iterative argument: + n=1: D0 falls because + n=2: D0 falls because D1 falls because + n=3: D0 falls because D1 falls because D2 falls because How good is this approach? How can we show that all dominos fall for any n >=1? "more compact" argument: + D0 falls because + Assume that all dominos will indeed fall over for any n + Pick an arbitrary value of n and call it k (why? well, we did assume that _____________________________) + Can we show that the NEXT domino (k+1) will fall if Dk falls? Yes...why? + Since k can be any value of n, what have we proved? ------------------------------------------------------------------------------- 4) The Gist Because we have a place to start and because any value works, we know that all "next values" work because we could start with an arbitrary value. The Civil Engineer at work: + What have we have not taken into account? + Pending research project.... ------------------------------------------------------------------------------- 5) First Principle of Mathematical Induction Also called Principal of Mathematical Induction (Weak Form) (adapted from Tremblay) Assume: the set of natural numbers N = {0, 1, ..., n} properties of natural numbers; e.g., P(n): 2*n is even for _____ 1st Principle: If P(s) is true and for all k >= s, P(k) is true implies that P(k+1) is true, then P(n) is true for all n >= s. Kind of hard to understand that... how about this? OK, keep (i) and now split (ii) up a bit more: Example: Prove that S(n)=0+1+...+n-1+n =(n)(n+1)/2 for n >= 0 Base case: S(0)? RHS = S(0) = 0 LHS = (0)(0+1)/2 = 0 LHS=RHS, so BC is OK Hypothesis: Inductive step: ------------------------------------------------------------------------------- 6) Solution to problem in (5): LHS: S(k+1) = 0+1+...+((k+1)-1)+(k+1) = 0+1+...+ (k) + (k+1) = (k)(k+1)/2 + (k+1) = ((k)(k+1)+2(k+1))/2 = (k^2+3k+2)/2 RHS: S(k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2 = (k^2+3k+2)/2 LHS=RHS, so the statement is proved! ------------------------------------------------------------------------------- 7) Generalized Second Principle of Mathemtical Induction also called Principle of Mathemtical Induction (Strong Form) Tremblay: If P(s), P(s+1),...,P(s+r-1) are true and for all n >= s+r, P(s), P(s+1,...,P(n-1) are all true implies P(n) is true, then P(n) is true for all n >= s Another version: Given list of items x0, x1, ..., xn, to prove that each has property P P(x0) is true If P(x0),P(x1),...,P(xk) are true for all k >= 0 Then P(x[k+1]) is true, The gist: Check if a property P works for a base case Assume P is true for a range of integers from the base case value to k-1 Check if P(k) (the next case) produces a true result. Since k is arbitrary, all values will work. Example: P: Every integer n >=2 is divisible by a prime number Base case: P(2) is true because 2/2 is legal and 2 is prime Inductive hypothesis: Assume P is true for 2 <= i < k So, P(2), P(3), ..., P(k-1) is true. Inductive step: Need to show P works for *next* integer, k Since k is arbitrary, then all cases will work. k is either prime or not prime 1) k is prime: 2) k is not prime: -------------------------------------------------------------------------------