Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 3 CS 15 251 Sept 5 2006 Induction II Inductive Pictures Fall 2006 Carnegie Mellon University Inductive Proof Standard Induction Least Counterexample All Previous Induction and Invaraints Theorem k 0 1 2 4 8 2k 2k 1 1 Try it out on examples 20 20 2 1 20 2 1 2 2 small 21 1 22 1 23 1 Sk 1 2 4 8 2k 2k 1 1 Use induction to prove k 0 Sk Sk 1 2 4 8 2k 2k 1 1 Use induction to prove k 0 Sk Sk 1 2 4 8 2k 2k 1 1 Use induction to prove k 0 Sk Establish Base Case S0 We have already checked 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 In Lecture 2 we also saw Inductive Definitions of Functions and Recurrence Relations Inductive Definition of n said n factorial 0 1 n n n 1 Definition of factorial 0 1 n n n 1 function Fact n F 1 For x 1 to n do F F x Return F n 0 returns 1 n 1 returns 1 n 2 returns 2 Does this bottom up program really compute n 0 1 n n n 1 function Fact n F 1 For x 1 to n do F F x Loop Return F Invariant F x here Loop Invariant F x True for x 0 If true after k iterations then true after k 1 iterations Inductive Definition of T n T 1 1 T n 4T n 2 n Notice that T n is inductively defined only 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 G 1 1 G 2 6 G 4 28 G 8 120 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 is the powers of two Inductive Proof of Equivalence G n 2n2 n T 1 1 T n 4 T n 2 n Inductive Proof of Equivalence G n 2n2 n T 1 1 T n 4 T n 2 n Inductive Proof of Equivalence Base G 1 1 and T 1 1 Induction Hypothesis T x G x for x n Hence T n 2 G n 2 2 n 2 2 n 2 G n 2n2 n T 1 1 T n 4 T n 2 n T n 4 T n 2 n by definition of T n 4 G n 2 n by I H 4 2 n 2 2 n 2 n by definition of G n 2 2n2 2n n 2n2 n G n by definition of G n We inductively proved the assertion that n 1 T n G n Giving a formula for T n with no sums or recurrences is called solving the recurrence for T n Solving Recurrences Guess and Verify Guess G n 2n2 n T 1 1 T n 4 T n 2 n Solving Recurrences Guess and Verify Guess G n 2n2 n T 1 1 T n 4 T n 2 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 That was another view of the same guess and verify proof of G n T n We showed that G T at the base case and that G satisfies the same recurrence relation Technique 2 Guess Form and Calculate Coefficients Guess T n an2 bn c for some a b c T 1 1 T n 4 T n 2 n Technique 2 Guess Form and Calculate Coefficients Guess T n an2 bn c for some a b c T 1 1 T n 4 T n 2 n Technique 2 Guess Form and Calculate Coefficients Guess T n an2 bn c for some a b c T 1 1 T n 4 T n 2 n Technique 2 Guess Form and Calculate Coefficients Guess T n an2 bn c for some a b c T 1 1 T n 4 T n 2 n 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 the special graphs called trees Graphs a root b Definition Graphs A graph G V E consists of a finite set V of vertices also called nodes and a finite set E of edges Each edge is a set a b of two different vertices n b A graph may not have self loops or multiple edges unless mentioned otherwise Visualization graphs A graph G V E consists of a finite set V of vertices also called nodes and a finite set E of edges Each edge is a set a b of two different vertices n b A graph may not have self loops or multiple edges unless mentioned otherwise 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 n b A directed graph may not have self loops or multiple edges unless mentioned otherwise Visualization 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 n b A directed graph may not have self loops or multiple edges unless mentioned otherwise Definition Rooted Tree A rooted tree is a directed graph with one special node called the root and the property that each node has a unique path from the root to itself Are these trees A rooted tree is a directed graph with one special node called the root and the property that each node has a unique path from the root to itself Definition Rooted Tree A rooted tree is a directed graph with one special node called the root and the property that each node has a unique path from the root to itself a root b Terminology Tree Child If u v 2E we say v is a child of u Parent If u v 2E we say u is the …
View Full Document
Unlocking...