Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 3 CS 15 251 Sept 6 2005 Induction II Inductive Pictures Fall 2005 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 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 Does this bottom up program really compute n 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 Return F 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 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 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 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 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 G n 2n2 n T 1 1 T n 4 T n 2 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 for T 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 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 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 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 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 parent of v Leaf If u has no children we say u is leaf Siblings If u and v have the same parent they are siblings a root b Terminology Tree 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 u is designated as the root of this tree a root b Classical Visualizations of Trees Here s the inductive rule If G is a single node Viz G If G consists of root r with sub trees T1 T2 Tk Viz G Viz T1 Viz T2 Viz Tk This visualization will be crucial to understanding properties of trees 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 called an outcome on each leaf Definition Labeled Trees A tree node labeled by S is a tree T V E with an associated function Node Label V S A tree edge labeled by S is a tree T V E with an associated function Edge Label E S was very illuminating Let s do something similar to illuminate the nature of T 1 1 T n 4T n 2 n T 1 1 T n 4T n 2 n For each n power of 2 we will define a tree V n that is node labeled by numbers This tree V n will give us an incisive picture of the recurrence relation T n Inductive Definition Of Labeled Tree V n T 1 V 1 T n 1 1 n 4 T n 2 n V n V n 2 V n 2 V n 2 V n 2 Inductive Definition Of Labeled Tree V n T 1 V …
View Full Document
Unlocking...