SUNY Geneseo Department of Computer Science

Pre- and Postconditions

Return to List of Lectures

Questions?

Algorithm Design

Sections 2.2 and 2.3 up to 2.3.2

• Robot
  • Draw squares, move, turn
  • Algorithms
• Postconditions = conditions true after algorithm finishes, implementor's job
• Preconditions = conditions that must hold for algorithm to work, client's job
• Side effects = changes to environment that algorithm produces, not accidental

What is abstraction?

• Preconditions and postconditions talked about without concern for implementation -- an example of abstraction
• "Abstract art" = weird, crazy
  • Doesn't represent real, recognizable things
  • Communicate, capture artist's image of beauty
  • Distill "beauty" to essentials, discard details
• Abstraction = focus on essentials, suppress details

Section 2.3.1 develops an algorithm for making a specific robot draw a square. How should that algorithm really be written for generality?

• Use parameters, pass robot as a parameter to "drawSquare"

        static void drawSquare( int size, Robot r ) {
            drawLine( size, r );
            r.turnRight();
            ...
        }

• Clients:

        drawSquare( 4, robbie );
        drawSquare( 10, robin );
        ...

• Use subclasses

        class DrawingRobot extends Robot {
            void drawSquare( int size ) {
                this.drawLine( size );
                this.turnRight();
                ...
            }

• Clients:

        DrawingRobot r = new DrawingRobot();
        r.drawSquare( 4 );

Example

• Find the point at which a line crosses the X axis

• Postconditions for exactly what this requires?
  • When does y = 0?
  • x is the value such that y = 0
  • Need equation of line!
    • y = mx + b, need m and b
  • x is the value such that mx + b = 0
• Preconditions for being able to do it?
  • Line must cross X axis
  • mx + b must somewhere = 0
  • m ≠ 0
• Algorithm for turning the preconditions into the postconditions?
  • Algorithm
    • input: m, b
    • output x = -b/m
  • Precision (in this case, mathematical form) of postcondition provided information you could use (in this case, via a bit of algebra) to deduce algorithm. Also provided insight into what inputs the algorithm would need.

Hand out problem set 1

Next

Theoretical reasoning about algorithms

Read Sections 3.1 - 3.4, 3.6