SUNY Geneseo Department of Computer Science

Induction and Algorithms, Part 1

Previous Lecture

Misc

Hand out Homework 1

Hand out Lab 5

Questions?

Reading - Section 7.1.2

Induction proofs on algorithms

Simple example, takeJourney

• Start with precondition, define parameter
• Theorem: if claim holds for first parameter should hold for next
  • Better: statement of general claim
• Base case: consider smallest possible n, 0 here
• Induction step: like we did Tuesday
  • Prove it works, then increase k each time

Implicit vs explicit induction variable

• Always something that changes during recursion to do induction on

Value-producing recursion

• Recursive factorial

Strong induction vs weak induction

• Strong induction = induction hypothesis that claim true for all numbers less than k, not just k-1
• Weak = hypothesis about only k-1
  • Induction step looks like "if such-and-such is true about k-1, then it's also true of k"
  • Good for recursions that solve size k problems by recursively solving size k-1 problem(s)
• vs...
  • Solving size k problems by solving problems of imprecisely known sizes less than k
  • e.g., sorting via "quicksort"

• Strong induction lets you use induction hypothesis about sorting sub-sections, no matter how big they end up being
• Book's example

Applying Induction to Algorithms

Unbalanced parentheses

• n "(" followed by 2n ")"

Mini-assignment: prove Tuesday's algorithm correct

    unbalancedParens( int n ) {
        if ( n > 0 ) {
            print "("
            unbalancedParens( n-1 )
            print "))"
        }
    }

Assume n >= 0

Induction on n

Base case: n = 0

• Test fails, algorithm does nothing
• Which is 0 "(" followed by 0*2 ")"

Assume it's true for k-1, k-1 >= 0, so k >0

• i.e., assume unbalancedParens(k-1) prints k-1 "(" followed by 2(k-1) ")"

For n = k...

• Test passes
• Print 1 "("
• Recursion prints k-1 "("
• Recurses, at end prints 2(k-1) ")" = 2k - 2
  • Or "recursion prints k-1 '(' followed by 2(k-1) =2k-2 ')' by the induction hypothesis"
• Last step prints "))"
• Adding all parentheses you get
  • k-1 + 1 = k "("
  • 2k - 2 + 2 = 2k ")"

Proof Examples

Multiplication by repeated addition:

    int multiply( int x, int y ) {
        if ( y == 0 ) {
            return 0;
        }
        else {           // y > 0 by precondition
            return x + multiply( x, y-1 );
        }
    }

• Prove this returns xy for all natural numbers x and y
• Induction on y
• Base case, y = 0
  • Algorithm returns 0
  • Which is correct because x * 0 always equals 0
• Induction step
  • Induction hypothesis: assume multiply( x, k-1 ) = kx - x, for some k-1 >= 0
  • Show multiply(x,k) = kx
    • k must be > 0
    • Algorithm executes "else"
    • Return x + multiply(x,k-1)
    • = x + kx - x
    • = kx

How about incorrect multiplication algorithm?

    int multiply( int x, int y ) {
        if ( y == 0 ) {
            return 0;
        }
        else {           // y > 0 by precondition
            return x + multiply( x, y+1 );
        }
    }

• Prove this correct:
• Induction on y
• Base case still works as above
• Induction hypothesis: multiply(x,k-1) = xk-x
• Show multiply(x,k) = xk
  • k > 0
  • Return x + multiply(x,k+1)
  • Oops! Doesn't match induction hypothesis

Next Lecture