Great Theoretical Ideas In Computer Science Steven Rudich Lecture 14 CS 15 251 Feb 26 2004 Induction II Inductive Pictures Spring 2004 Carnegie Mellon University Inductive Proof Standard Induction Least Counter example All Previous Induction Inductive Definition Recurrences Recursive Programming Theorem k 0 1 2 4 8 2k 2k 1 1 Try it out on small examples 20 21 1 20 21 22 1 20 21 22 23 1 Sk 1 2 4 8 2k 2k 1 1 Use induction to prove k 0 Sk Establish Base Case S0 We have already check it Establish Domino Property k 0 Sk Sk 1 Inductive Hypothesis Sk 1 2 4 8 2k 2k 1 1 Add 2k 1 to both sides 1 2 4 8 2k 2k 1 2k 1 2k 1 1 FUNDAMENTAL LEMMA OF THE POWERS OF TWO The sum of the first n powers of 2 is one less than the next power of 2 Yet another way of packaging inductive reasoning is to define an invariant Invariant adj 1 Not varying constant 2 mathematics Unaffected by a designated operation as a transformation of coordinates Yet another way of packaging inductive reasoning is to define an invariant Invariant adj 3 programming A rule such as the ordering an ordered list or heap that applies throughout the life of a data structure or procedure Each change to the data structure must maintain the correctness of the invariant Invariant Induction Suppose we have a time varying world state W0 W1 W2 Each state change is assumed to come from a list of permissible operations We seek to prove that statement S is true of all future worlds Argue that S is true of the initial world Show that if S is true of some world then S remains true after one permissible operation is performed Odd Even Handshaking Theorem At any party at any point in time define a person s parity as ODD EVEN according to the number of hands they have shaken Statement The number of people of odd parity must be even Initial case Zero hands have been shaken at the start of a party so zero people have odd parity If 2 people of different parities shake then they both swap parities and the odd parity count is unchanged If 2 people of the same parity shake they both change But then the odd parity count changes by 2 and remains even Inductive Definition of n said n factorial 0 1 n n n 1 0 1 n n n 1 F 1 For x 1 to n do F F x Return F Program for n 0 1 n n n 1 F 1 For x 1 to n do F F x n 0 returns 1 Return F n 1 returns 1 n 2 returns 2 Program for n 0 1 n n n 1 F 1 For x 1 to n do F F x Return F Loop Invariant F x True for x 0 If true after k times through true after k 1 times through Inductive Definition of T n T 1 1 T n 4 T n 2 n Notice that T n is inductively defined for positive powers of 2 and undefined on other values Inductive Definition of T n T 1 1 T n 4T n 2 n Notice that T n is inductively defined for positive powers of 2 and undefined on other values T 1 1 T 2 6 T 4 28 T 8 120 Guess a closed form formula for T n Guess G n G n 2n2 n Let the domain of G be the powers of two Two equivalent functions G n 2n2 n Let the domain of G be the powers of two T 1 1 T n 4 T n 2 n Domain of T are the powers of two Inductive Proof of Equivalence Base G 1 1 and T 1 1 Induction Hypothesis T x G x for x n G n 2n2 n T 1 1 T n 4 T n 2 Hence T n 2 G n 2 2 n 2 2 n 2 n T n 4 T n 2 n 4 G n 2 n 4 2 n 2 2 n 2 n 2n2 2n n 2n2 n G n We inductively proved the assertion that G n T n Giving a formula for T with no sums or recurrences is called solving the recurrence T Solving Recurrences Guess and Verify Guess G n 2n2 n Verify G 1 1 and G n 4 G n 2 n Similarly T 1 1 and T n 4 T n 2 n So T n G n Technique 2 Guess Form and Calculate Coefficients Guess T n an2 bn c for some a b c Calculate T 1 1 a b c 1 T n 4 T n 2 n an2 bn c 4 a n 2 2 b n 2 c n an2 2bn 4c n b 1 n 3c 0 Therefore b 1 c 0 a 2 A computer scientist not only deals with numbers but also with Finite Strings of symbols Very visual objects called graphs And especially especially the special graphs called trees GRAPHS a root b Definition Graphs A graph G V E consists of a finite set V of vertices nodes and a finite set E of edges Each edge is a set a b of two different vertices A graph may not have self loops or multiple edges Definition Directed Graphs A graph G V E consists of a finite set V of vertices nodes and a finite set E of edges Each edge is an ordered pair a b of two different vertices Unless we say otherwise our directed graphs will not have multi edges or self loops Definition Tree A tree is a directed graph with one special node called the root and the property that each node must a unique path from the root to itself Child If u v 2E we sav is a child of u Parent If u v 2E we say u is the parent of u Leaf If u has no children we say u is leaf Siblings If u and v have the same parent they are siblings Descendants of u The set of nodes reachable from u including u Sub tree rooted at u Descendants of u and all the edges between them where u has been designated as a root Classic Visualization Tree Inductive rule If G is a single node Viz G If G consists of root r with sub trees T1 T2 Tk Viz G Vuz T1 Viz T2 Viz Tk I own 3 beanies and 2 ties How many beanie tie combos might I wear to the ball tonight Choice Tree A choice tree is a tree with an object called a choice associated with each edge and a label on each leaf Definition Labeled Tree A tree node labeled by S is a tree T V E with an associated function Label1 V to S A tree edge labeled by S is a tree T V E …
View Full Document
Unlocking...