SUNY Geneseo Department of Computer Science

Introduction to Theory

Previous Lecture

Questions?

Efficiency & fastest = fewest steps?

• What if one step is real slow?
• Matters in principle, but not in practice

Reading Summary

Sections 3.1 - 3.3, 3.6

Proving/knowing that an algorithm works correctly

2 ways

• Testing - sure implementation works for some inputs
• Proof - sure that it works for every input, but not that specific implementation is OK

Rigor & formality

• Rigor = correctness
• Formality = following math conventions

3.6 about efficiency

• Fewer steps = faster execution
• How to find number of steps for an algorithm

Examples

An algorithm to make a robot paint a line n tiles long:

    // In some subclass of Robot...
    paintLine( n )
        repeat n times
            this.paint( ...some color... )
            this.move()

How many robot messages (paint, move, turnLeft, etc.) does this send while painting an n-tile line?

• 2 robot messages, but inside loop
• Repeats n times
• Therefore total number of messages = 2n

What does this suggest about the algorithm's concrete running time?

• Time proportional to n
• time = c n

What does it mean to say this algorithm is "correct?"

• If preconditions are satisfied at start...
  • Then postconditions satisfied at end
• Preconditions: No obstacles on n tiles ahead of robot, faces along the future line, standing on first tile
• Postconditions: There's a line n tiles long, immediately behind the robot, and robot faces original direction

An algorithm for filling an n-by-n square:

    paintSquare( n )
        while n > 0
            this.paintLine( n )
            this.turnRight()
            this.move()
            this.turnRight()
            this.move()
            if n > 1
                this.paintLine( n )
                this.turnLeft()
                this.move()
                this.turnLeft()
                this.move()
            end of if
            n = n - 2
        end of while

Yuck! Does this really work?

Preconditions: robot is at lower right corner of square, facing along bottom line of square, no obstacles in or 1 tile beyond future square

Postconditions: Colored square forward and right of robot's original position

Proof basically follows the statements of the algorithm, deducing robot's position, orientation, etc., and existence of lines, from each. Tracking much of this in a picture is helpful. "paintLine" messages can be dealt with as abstractions, you can always conclude that its postcondition holds after message if precondition held before, without remembering what's inside the "paintLine" method.

Next

Mini-assignment: work out theoretical running time of filled-square algorithm, in terms of n

Experimentation

Read Sections 4.1 through 4.7

Next Lecture