SUNY Geneseo Department of Computer Science

Introduction to Theory

Previous Lecture

Misc

Turn in Lab 1 solutions

New Friday office hours: 2:30 - 4:00, not 1:30 - 3:00

Questions?

Reading Summary

Sections 3.1, 3.2, 3.6

About algorithms and whether a method is an algorithm

How to prove a method is an algorithm

• The method must work under all circumstances

Conditions for a method to be an algorithm

• All postconditions must be met given that the preconditions are true

Whether an algorithm is efficient

Best way to determine if algorithm is correct is proof

Execution time analyses?

• Analyses are very accurate relative to real world
• Very common analyses, (more common than correctness?)

Some Theoretical Analyses

This algorithm (or expression) supposedly computes the number that is fraction f of the way between numbers n1 and n2

    partOfTheWay( n1, n2, f )
        // Precondition: n1 <= n2
        return f * n2 + (1-f) * n1

• (The algorithm has applications in graphics, namely interpolating or extrapolating a line given two points on it -- the algorithm is applied separately to the points' x and y coordinates)
• Prove that this algorithm really does return the number fraction f of the way between n1 and n2

• n1 <= n2
• What number is fraction f of the way between n1 & n2?
  • number = n1 + f * ( n2 - n1 )
  • = n1 + f * n2 - f * n1
  • = (1-f) * n1 + f * n2
• Execution time?
  • Count.... number of steps
  • Step = operation in expressions
  • "f * n2 + (1-f) * n1" executes 4
    • (multiply, add, subtract)
  • "n1 + f*(n2 - n1)" executes 3

Resource analysis example:

• How many robot messages (move, turnLeft, turnRight, paint) does the following algorithm send in order to draw a line n tiles long?

    // In some subclass of Robot:
    drawLine( int n, Color c ) {
        for ( i = 0; i < n; i++ ) {
            this.paint( c )
            this.move()
        }
    }

• Robot messages are "paint" and "move"
• 2 of them
• But inside a loop, so every time through loop you do 2 operations
• Loop repeats n times
• So total number of steps = 2n
• What can you conclude from this about the execution time of the algorithm?
  • Time depends on n, time increases with n
  • Time is proportional to n
    • i.e., time = c * n for some machine-dependent c

Here's an algorithm that supposedly makes a robot paint the border of its room (i.e., the tiles adjacent to the walls):

    // In some subclass of Robot:
    paintBorder( Color c ) {
        // Preconditions: There are no
        // obstructions other than the walls in the
        // room
        while ( this.okToMove() ) {
            this.move()
        }
        // robot is at wall
        this.paintSide( c )
        this.paintSide( c )
        this.paintSide( c )
        this.paintSide( c )
        this.paintSide( c )
    }
    paintSide( Color c ) {
        this.turnLeft()
        while ( this.okToMove() ) {
            this.paint( c )
            this.move()
        }
    }

• Prove that this algorithm really does leave every tile adjacent to a wall color c
• Modus ponens: way of deducing things
  • P implies Q
  • P is true
  • Then Q must be true
• No time to finish, but did see how to deduce conditions after a step from those before it, work such deductions from beginning of algorithm through to end.

Next

Experimentation (the scientific method) in CS

Read Sections 4.1 - 4.7

Mini-assignment: Design an experiment to test the ideas above about the execution time of the draw-a-line algorithm (i.e., that time is proportional to n).

Next Lecture