SUNY Geneseo Department of Computer Science

Introduction to Induction

Previous Lecture

Misc

CS Department conversation re recent swastika vandalism

• Thurs, Feb. 12, 12:45
• South 309

Questions?

Induction step corresponds to what in algorithms?

• Recursive message!

Recursion and Correctness

Mini-assignment: Print an unbalanced string of parentheses, n "(" followed by 2n ")"

• (())))

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

• How do/can you know this algorithm is correct?
  • Testing with an inductive feel -- test for input k, then input k+1
  • Make sure it works for very small number, e.g., 1, then test for k and k+1
  • Test for 1, then assume it works for k and test for k+1, then argue that it works for 1, 2, ... k+1, k+2, ...
  • Why does testing k and k+1 help in general?
    • Testing by itself doesn't
    • Look at the code, prove that if the algorithm works on k then it works on k+1
    • No matter what k, k+1 are
    • This was an induction proof

Read Section 7.1.1

• Induction in math is generalizing individual observations to universal rules
• Individual observation = base case
• Induction step
  • Test for small numbers, if this works it should work for larger numbers to infinity
• Base case and induction step comprise the proof
• Examples

Mathematical Induction Example

Issue that shows up as a limiting factor in how efficiently a lot of computations can be done:

• If you have n things, and need to find some subset of them, there are 2ⁿ possible subsets
• e.g., company wants to find the set of products to manufacture that maximizes profit, divide n players into two teams of roughly equal ability, ...

Prove the basic mathematical limit -- that every set of n items has 2ⁿ possible subsets.

Induction on the size of the set = n

• "Induction on" identifies thing that varies

Base case: empty set, i.e., { }, n = 0

• Goal: prove "it" is true for this case
• i.e., prove 0-element set has 2⁰ subsets
• Only subset is {}, i.e., 1 subset, and 2⁰ = 1

Induction step:

• Induction hypothesis: Assume every set with k elements has 2^k subsets
• Induction: Show that every set with k+1 elements has 2^k+1 subsets

• Total number of subsets is 2^k * 2 = 2^k+1.

Playact the proof:

• Emily: true for 0 elements because only subset is {}
• Jackie: true for 1 element because subsets either have that element or don't, so 2 of them
• Pat: true for {a,b}, subsets are {a}, {b}, {a,b}, {} = 4 subsets, 2² = 4
• Ryan: {a,b,c} has subsets {a} {b} {c} {a b } {a c} {b c} {a b c} {}
• Jackie: 4 elements: set with 4 elements has 3 elements plus 1 more, Ryan just proved that the 3 elements make 2³ = 8 subsets, remaining 1 element yields 2¹ = 2 subsets, combining those 2 with the 8 yields 8*2 = 16 possibilities = 2⁴.
• Lisa: 5 elements. set of 5 elements has 2⁵ subsets. By Jackie's reasoning, and her result that 4 element sets have 2⁴ subsets, plus my 1 other element.

Applying Induction to Algorithms

Unbalanced parentheses, n "(" followed by 2n ")"

• Mini-assignment: prove the above algorithm for this problem correct

Read Section 7.1.2

Next Lecture