SUNY Geneseo Department of Computer Science
Induction
and Algorithms, Part 2
{Date}
CSci 141, Spring 2004
Prof. Doug Baldwin
Return
to List of Lectures
Previous Lecture
Questions?
Proofs, e.g., on tests?
- Clear and convincing reason why something is true
- Prose usually good (also pictures, formulas)
Induction steps?
- "If I somehow know that my theorem is
true of a particular number k-1, what
would I know about k?"
- Induction hypothesis: "...I somehow know
theorem is true of k-1"
- Induction: "... what would I know about k"
- Act of fantasy: pretend theorem is true of k-1,
where does that get you
Examples of Inductive Correctness Proofs
Prove that the following draws a red line n tiles
long, starting at the tile the robot is initially on,
and leaving the robot one tile past the end of the
line
// In some subclass of Robot...
void redLine( int n ) {
if ( n > 0 ) {
this.paint( Color.red );
this.move();
this.redLine( n-1 );
}
}
Induction on n
- Base case, n = 0
- Robot doesn't move,
- Which leaves a red line 0 tiles long
- Such a line looks like this:
- Or base case of n = 1
- Certainly possible
- Takes longer to think through
- n = 0 is a legal parameter, ought to be
covered by correctness proof
- Induction hypothesis: redLine(k-1) draws
k-1 red tiles in a line, and leaves robot
standing after the last,
assuming k-1 is a natural number
- Show redLine(k) draws k red tiles and leaves
robot standing after last
- Since k-1 >= 0, k > 0
- Algorithm passes first test
- Paints 1 tile
- Moves to next
- redLine(k-1)
- Which draws k-1 more
tiles, by induction
hypothesis
- So that total number of
painted tiles is k, and robot is after
the last one
The howManyDigits method from Chapter 6
int howManyDigits( int n ) {
if ( n < 10 ) {
return 1;
}
else {
return 1 + howManyDigits(floor(n/10));
}
}
- Prove that this returns the number of digits in
the decimal representation of n, for all integers
n >= 0.
- [ Not essential parts of proof because subsumed
in general base case later:
- Base case, n = 0
- 0 < 10, so algorithm returns 1
- 0 is a 1-digit number. Correct
- Base case, n = 1
- 1 < 10, algorithm returns 1, which is correct ]
- Base cases, n < 10
- 0, 1, 2, ... 9
- n < 10, so algorithm returns 1,
- n is a one-digit number
- Induction hypothesis: suppose
howManyDigits(k/10) returns # of digits in
k/10
- (Or strong induction: howManyDigits(x)
returns number of digits in x for all x < k)
- Show howManyDigits(k) returns number of digits
in k
- k/10 >= 0, k/10 integer by precondition
- if k/10 = 0, k = 0, test fails, algorithm
returns 1, which is correct
- if k/10 > 0, k >= 10 so algorithm
returns 1 + (# of digits in k/10)
- (# of digits in k/10) is one less than
# of digits in k, so the above sum
is the number of digits in k
Performance Analysis of Recursive Algorithms
For example, just how many disk moves does the
towers of Hanoi algorithm require?
solve( n, source, dest, spare )
if n > 0
this.solve( n-1, source, spare, dest )
this.move( source, dest )
this.solve( n-1, spare, dest, source )
Number of moves is going to depend on n,
M(n) is number of disk moves towers of
Hanoi
algorithm does to solve an n-disk puzzle
M(n) = 2 M(n-1) + 1 if n > 0
But when n=1, M(n) = 1
By analogy, maybe M(n) = 2n - 1
Read Section 7.2.1
Next Lecture