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 10Slide 11Inductive Definition of T(n)Guess a closed form formula for T(n). Guess G(n)Two equivalent functions?Inductive Proof of EquivalenceSlide 16Slide 17Slide 18Solving Recurrences: Guess and VerifySlide 20Slide 21Technique 2 Guess Form and Calculate CoefficientsSlide 23Slide 24Slide 25Slide 26GraphsDefinition: GraphsVisualization: graphsDefinition: Directed GraphsVisualization: Directed graphsDefinition: Rooted TreeAre these trees?Slide 34Terminology: TreeSlide 36Classical Visualizations of TreesSlide 38Slide 39Slide 40Choice TreeDefinition: Labeled TreesSlide 43Slide 44Inductive Definition Of Labeled Tree V(n)Slide 46Slide 47Slide 48Slide 49Slide 50Can prove Invariant: T(n) = (sum of labels in V(n))Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58New Recurrence T(n) = 2T(n/2) + nSlide 60Slide 61Slide 62Slide 63Slide 64The Lindenmayer GameAristid Lindenmayer (1925-1989)The Koch GameSlide 68Slide 69Koch CurveSlide 71Slide 72Hilbert’s space filling curvePeano’s gossamer curveSierpinski’s triangleLindenmayer 1968Slide 77Inductive LeafSlide 79Slide 80Much more stuff atStudy BeeInduction II:Inductive PicturesGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 3 Sept 5, 2006 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, SkSk´ “1+2+4+8+…+2k = 2k+1 -1”Use induction to prove k¸0, SkSk´ “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! ? 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; Loop Invariant: F=x!True for x=0. If true after k iterations, then true after k+1 iterations. Return F }// Loop Invariant: F=x! hereInductive 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.G(1)=1 G(2)=6 G(4)=28 G(8)=120Two 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 EquivalenceG(n) = 2n2 - nT(1) = 1T(n) = 4 T(n/2) + nInductive Proof of EquivalenceG(n) = 2n2 - nT(1) = 1T(n) = 4 T(n/2) + nInductive 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 [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)]G(n) = 2n2 - nT(1) = 1T(n) = 4 T(n/2) + nWe 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 VerifyT(1) = 1T(n) = 4 T(n/2) + nGuess: G(n) = 2n2 – nSolving Recurrences: Guess 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 2Guess Form and Calculate CoefficientsGuess: T(n) = an2 + bn + c for some a,b,cT(1) = 1T(n) = 4 T(n/2) + nTechnique 2Guess Form and Calculate CoefficientsGuess: T(n) = an2 + bn + c for some a,b,cT(1) = 1T(n) = 4 T(n/2) + nTechnique 2Guess Form and Calculate CoefficientsGuess: T(n) = an2 + bn + c for some a,b,cT(1) = 1T(n) = 4 T(n/2) + nTechnique 2Guess 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 treesbrootaGraphsDefinition: 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)Visualization: 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 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)Visualization: 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: Rooted TreeA 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
View Full Document