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?

Induction steps?

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

[0 Red Tiles]

[k Red Tiles as 1 + (k-1) Red Tiles]

The howManyDigits method from Chapter 6

    int howManyDigits( int n ) {
        if ( n < 10 ) {
            return 1;
        }
        else {
            return 1 + howManyDigits(floor(n/10));
        }
    }

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