SUNY Geneseo Department of Computer Science

Induction and Algorithms, Part 1

Previous Lecture

Questions?

Binary digits needn't be static

• But no obvious object to handle it

A Review/Preview

Recall the bracket algorithm

    // In some subclass of Robot...
    bracket( n )
        if n > 1
            this.paint( Yellow )
            this.move()
            this.bracket( n-1 )
            this.move()
            this.paint( Yellow )
        else
            this.paint( Yellow )
            this.turnLeft()

Contrast to iterative version

• Two loops, careful about ends/starts of loops
• vs one recursion -- simpler structure

Summary of how this works

• Hey! The "summary" was really an induction argument for why the algorithm works!

Proofs about Recursive Algorithms

Read Section 7.1.2

Way to prove things about recursive algorithms

Use small problem to prove large problems

Base case

• Prove algorithm eventually stops
• Really: Proves algorithms correct for smallest problems, which is where recursion stops

Induction hypothesis

• Only use when preconditions all hold

Can be used for algorithms that return values

Weak vs strong induction

• Strong induction = claim is true for all naturals
• Weak induction = use smaller set of numbers
• ???
• Really:
  • Induction step, prove something about k
  • Strong: assume true for all numbers < k
  • Weak induction: assume true just for k-1

Example Proofs

What do you think this prints?

• 2n+1 A's
• Odd number of A's

    printA( n )
        if n > 1
            print "AA"
            printA( n - 1 )
        else
            print "A"

Prove it

• 2n+1 A's
• Or maybe 2n -1 -- when n = 1 algorithm only prints 1 A

Prove printA(n) prints 2n -1 A's

• Base case, n = 1 (induction on n)
  • Executes "else", prints 1 A
  • 1 = 2*1 - 1 = 2n - 1
• k-1, assume k-1 > 1 and printA(k-1) prints 2(k-1) - 1 = 2k - 3 A's
  • (You actually want to assume that k-1 >= 1, so that k-1 can be a number to which the base case applies)
  • Implies k > 1 so printA(k) executes "then",
    • Prints "AA"
    • Calls printA again which prints 2(k-1) - 1 = 2k - 3 A's
    • By induction hypothesis

Mini-assignment: finish proof

Next Lecture