SUNY Geneseo Department of Computer Science

Induction and Algorithms, Part 2

Previous Lecture

Misc

Hand out Lab 5

Questions?

The "printA" Algorithm

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

Mini-assignment: finish proving that it prints 2n-1 A's

Proof by induction on n

• Base case, n = 1
  • printA(1) executes "else", prints 1 A
  • 1 = 2*1 - 1 = 2n - 1
• Induction hypothesis: assume k-1 >= 1 and printA(k-1) prints 2(k-1) - 1 = 2k -3 A's
• Show printA(k) prints 2k - 1 A's
  • k > 1, so printA(k) executes "then"
  • Prints 2 A's
  • Calls printA(k-1), which prints 2k - 3 A's
    • (by induction hypothesis)
  • Total number of A's printed = 2 + 2k - 3 = 2k - 1

Prove (by induction) Friday's other claim about this algorithm: that it prints an odd number of A's

• Base case, n = 1
  • Algorithm prints 1 A, which is odd
• Induction hypothesis, assume it works for n = k-1, i.e., printA(k-1) prints an odd number of A's
  • (implicitly k-1 >= 1)
• Induction step, show when n = k, printA(k) prints an odd number of A's
  • k > 1 so printA prints 2 A's
  • Calls printA(k-1) which prints an odd number of A's
  • Total number of A's is odd, because odd number printed recursively + 2 must be odd
    • Definition of odd integer is an integer of the form a = 2i + 1
    • i.e., for k-1, algorithm prints 2i + 1 A's for some integer i, (2i + 1) + 2 = (2i + 2) + 1 = 2(i+1) + 1 which is odd by definition

Towers of Hanoi

    solve( n, source, dest, spare )
        if n > 0
            solve( n-1, source, spare, dest )
            move 1 disk from source to dest
            solve( n-1, spare, dest, source )

Prove that this really always solves an n-disk towers of Hanoi puzzle, n >= 0

• i.e., that solve( n, source, dest, spare ) moves an n-disk tower from source to dest and never puts big disk on small (or drops disk off pole)

Induction on number of disks, n

• Base case, 1 disk
  • Recursively moves 0 disks, does nothing
  • Move the 1 disk to dest
  • Recursively does nothing
  • QED
• Or n = 0
  • Algorithm does nothing
  • Never puts big on small
  • Does move all n disks from source to dest
    • Vacuous truth: any statement about all members of an empty set is true
• Induction hypothesis: solve(n-1...) where n-1>= 0 will correctly move n-1 disk tower from source to dest
• Show solve( n, .... ) correctly moves n-disk tower
  • Algorithm recursively moves n-1 disks to spare pole, correct by induction hypothesis
  • Moves bottom-most (biggest) to dest
    • (No violations of big-on-small)
  • Second recursion correctly (by induction) moves n-1 disks from spare to dest
    • (No big-on-small since all smaller than disk already on dest)

Next

Deriving the number of steps a recursive algorithm executes

Read Section 7.2.1

Next Lecture