Induction II: Inductive PicturesSlide 2Slide 3Sk´ “1+2+4+8+…+2k = 2k+1 -1” Use induction to prove k¸0, SkSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Inductive Definition of T(n)Slide 12Guess a closed form formula for T(n). Guess G(n)Two equivalent functions?Inductive Proof of EquivalenceSlide 16Solving Recurrences: Guess and VerifySlide 18Technique 2 Guess Form and Calculate CoefficientsSlide 20GraphsDefinition: GraphsDefinition: Directed GraphsDefinition: TreeTerminology: TreeSlide 26Classical Visualizations of TreesSlide 28Slide 29Slide 30Choice TreeDefinition: Labeled TreesSlide 33Slide 34Inductive Definition Of Labeled Tree V(n)Slide 36Slide 37Slide 38Slide 39Slide 40Can prove Invariant: T(n) = (sum of labels in V(n))Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53The Lindenmayer GameSlide 55Slide 56Aristid Lindenmayer (1925-1989)The Koch GameSlide 59Slide 60Slide 61Slide 62Koch CurveSlide 64Slide 65Hilbert’s Space Filling CurvePeano-Gossamer CurveSierpinski TriangleLindenmayer (1968)Lindenmayer 1968Inductive LeafSlide 72Slide 73Study BeeInduction II:Inductive PicturesGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 3 Sept 6, 2005 Carnegie Mellon UniversityInductive Proof: “Standard” Induction“Least Counter-example”“All Previous” InductionandInvaraintsTheorem? (k ≥ 0)1+2+4+8+…+2k = 2k+1 -1Try it out on small examples:20 = 21 -120 + 21 = 22 -120 + 21 + 22= 23 -1Sk´ “1+2+4+8+…+2k = 2k+1 -1”Use induction to prove k¸0, SkEstablish “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 -1Add 2k+1 to both sides:1+2+4+8+…+2k + 2k+1= 2k+1 +2k+1 -11+2+4+8+…+2k + 2k+1= 2k+2 -1Fundamental 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 Definitionsof FunctionsandRecurrence RelationsInductive Definition of n! [said “n factorial”]0! = 1n! = n × (n-1)!Definition of factorial0! = 1; n! = n × (n-1)!function Fact(n) { F:=1; For x = 1 to n doF:=F*x; Return F}Does this bottom-upprogram really compute n! ?Definition of factorial0! = 1; n! = n × (n-1)!function Fact(n) { F:=1; For x = 1 to n doF:=F*x; Return F}Does this bottom-upprogram really compute n! ? n=0 returns 1n=1 returns 1n=2 returns 20! = 1; n! = n × (n-1)!function Fact(n) { F:=1; For x = 1 to n doF:=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) = 1T(n) = 4T(n/2) + nNotice that T(n) is inductively defined only for positive powers of 2, and undefined on other values.Inductive Definition of T(n)T(1) = 1T(n) = 4T(n/2) + nNotice 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)=120Guess a closed form formula for T(n).Guess G(n)G(n) = 2n2 - nLet the domain of G be the powers of two.Two equivalent functions?G(n) = 2n2 - nLet the domain of G be the powers of two.T(1) = 1T(n) = 4 T(n/2) + nDomain of T is the powers of two.Inductive Proof of EquivalenceInductive Proof of EquivalenceBase: G(1) = 1 and T(1) = 1Induction Hypothesis:T(x) = G(x) for x < n Hence: T(n/2) = G(n/2) = 2(n/2)2 – n/2T(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 - nT(1) = 1T(n) = 4 T(n/2) + nWe 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: Solving Recurrences: Guess and VerifyGuess and VerifyT(1) = 1T(n) = 4 T(n/2) + nGuess: G(n) = 2n2 – nVerify: G(1) = 1 and G(n) = 4 G(n/2) + n Similarly:T(1) = 1 and T(n) = 4 T(n/2) + nSo 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 2Technique 2Guess Form and Calculate CoefficientsGuess Form and Calculate CoefficientsGuess: T(n) = an2 + bn + c for some a,b,cCalculate: 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 = 0Therefore: b=-1 c=0 a=2T(1) = 1T(n) = 4 T(n/2) + nA computer scientist not only deals with numbers, but also withfinite strings of symbolsVery visual objects called graphsAnd especially the special graphs called treesbrootaGraphsGraphsDefinition: GraphsDefinition: GraphsA 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 GraphsDefinition: Directed GraphsA 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: TreeDefinition: TreeA 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. brootaTerminology: TreeTerminology: 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.brootaTerminology: TreeTerminology: 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.)brootaClassical Visualizations of TreesClassical Visualizations of TreesHere’s the inductive rule:If G is a single nodeViz(G) =If G consists of root r with sub-trees T1, T2, …, TkViz(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?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.Choice TreeChoice TreeDefinition: Labeled TreesDefinition: Labeled TreesA tree “node labeled by S” is a tree T = (V,E)
View Full Document