SUNY Geneseo Department of Computer Science

Induction and Algorithms, Part 2

Return to List of Lectures

Misc

Problem set 5 due today

Lab 3 due tomorrow

Phi Beta Kappa Lecture

• David Kendall, "The Great War Today"
• 4:30 PM, Newton 203

Questions?

Induction Proofs about Recursion

Example

• Prove that the algorithm for printing n, n-2, n-4, ... down to either 1 or 0, and then all the skipped numbers (..., n-3, n-1) up to n-1 that we developed a couple of days ago is correct:

        print( n )
            if n > 1
                output n
                print( n-2 )
                output n-1
            else
                output n

• Proof by induction on n
  • Base case
    • n = 0 (needs to print 0)
      • "if n > 1" fails, algorithm executes "else"
      • Which prints n = 0
      • Then algorithm stops
    • n = 1 (needs to print 1)
      • "n > 1" still fails, algorithm prints n = 1
  • Induction
    • Hypothesis
      • Assume print(k) will print k, k-2, ..., 1 or 0, ... k-3, k-1, for some k >= 0
    • Show print(k+2) will print k+2, k, k-2, ... 1 or 0, ... k-1, k+1
      • Consider print(k+2)
      • "if n > 1" succeeds
      • Print k+2
      • Recursively print(k), prints k, k-2, ... 1 or 0, ... k-3, k-1.
      • After recursion, prints k+1
• Morals:
  • Induction hypothesis relates to what you show with it exactly the same way recursive calls related to original call
  • induction hypothesis "thinks" about recursion in exactly the right way
  • Multiple base cases in algorithm correspond to multiple base cases in induction

Another Example

• Towers of Hanoi
• Demonstration of problem/solution at http://pirate.shu.edu/~wachsmut/Java/Hanoi/index.html
• This algorithm allegedly solves a Towers of Hanoi puzzle, where source, dest, and spare are poles.
  • Specifically, the algorithm is supposed to move the top n disks from source to dest via spare without violating any of the rules of the puzzle (precondition: the top n disks on source are the smallest n disks in the puzzle; no rules are violated)

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

• Explanation by induction on n
• Base case, n = 0
  • "if n > 0" fails
  • Algorithm does nothing
  • Algorithm has moved 0 disks and violated no rules
• Induction step
  • Assume tower( k-1, source, dest,spare ) moves k-1 disks, k-1 >= 0
  • Show tower (k, ... ) moves k disks
    • "if n > 0" succeeds
    • Algorithm executes tower( k-1, source,spare,dest)
    • By induction hypothesis, k-1 disks move to spare pole without violating rules
    • Then moves 1 disk to destination, OK since all smaller disks are on spare pole
    • Finally, moves k-1 disks from spare to dest, works OK by induction hypothesis

Hand out problem set 6

Hand out lab 4

Next

Formal tools for reasoning about the performance of recursive algorithms

Read section 7.2.1