SUNY Geneseo Department of Computer Science

Experimentation

Previous Lecture

Questions?

Algorithm Analysis

Mini-assignment: how many Robot messages in Wednesday's fill-a-square algorithm?

• (Oops - which has a bug that makes it harder to analyze than intended)
• "Loop invariant" = statement true on every iteration

    while n > 0
        ...
        n = n -2

• Invariant : n is remaining number of rows

    ...
    paintLine(n)

• Invariant: n is length of a row
• These two implicit invariants are inconsistent with each other!
• The corrected algorithm

    paintSquare( n )
        for i = n down to 1, decrementing i by 2
            // Block 1
            this.paintLine( n )
            this.turnRight()
            this.move()
            this.turnRight()
            this.move()
            if i > 1
                // Block 2
                this.paintLine( n )
                this.turnLeft()
                this.move()
                this.turnLeft()
                this.move()
            end of if
        end of for

    paintLine
        repeat n times
            this.paint( ...some color... )
            this.move()

First solution

• c1 = time to execute block 1 once
• c2 = time to execute block 2 once
• Block 1 has 5n total messages
• Block 2 has 5(n - 1) messages
• Time = c1n + c2(n-1)

But paintLine takes time proportional to n, so

• Block 1 takes 4 + 2n messages each iteration
• Same for block 2
• Each block is done roughly n/2 times
• So total number of messages
  • = n/2(4 + 2n + 4 + 2n)
  • = n/2(8 + 4n)
  • = 4n + 2n²
• Time should be proportional to 4n + 2n²

How about rounding n/2?

• floor(x) = x rounded down to an integer
  • floor(2.1) = 2 = floor(2.9) = floor(2)
• ceiling(x) = x rounded up to an integer
  • ceiling(2.9) = 3 = ceiling(2.1) = ceiling(3)

Experimentation

Reading Summary: sections 4.1 through 4.7

Verification

Experimentation:

• Form hypothesis
• Make prediction
  • Before running experiment
• Design experimental procedure
• Perform experiment, collect data
  • Many measurements, use average
• Analyze data
• Conclusion

Error

• Systematic
• Random

Measuring time

• Turn off other programs

An Experiment

Design and conduct an experiment to test the hypothesis that the running time of a real "paintSquare" method is proportional to the number of Robot messages derived in the mini-assignment

Started with a program that defined an appropriate subclass of Robot, added code to run experiment and collect data.

See the Resulting Program

This was mainly experiment design, including things like devising and inserting instrumentation code, thinking briefly about controlling outside influences by disconnecting from any network and stopping other programs, etc.

But we also noted that we had a hypothesis from the result of the theoretical analysis done at the beginning of class.

Next

Do at least part of the experiment, and then start talking about conditionals.

No reading or mini assignments.

Next Lecture