SUNY Geneseo Department of Computer Science

Experimentation, Part 2

Previous Lecture

Misc

Hand out Lab 3

• 2nd page was missing -- complete copies in my office, cs dept., lab, and on Web

Questions?

Experimentation

Friday we made theoretical predictions about the execution time of an algorithm for filling a square, and set up an experiment to test those predictions.

Hypothesis: The execution time of this algorithm is proportional to 4n + 2n², where n is the length of a side of the square

Procedure:

• Paint squares for n = 6, 8, 10, and 12
• For each, create a new robot room and robot, then time "paintSquare" for that n
• Program prints time and ratio of time to 4n + 2n².
• Shut down, e.g., word processor, etc.

Prediction? printed ratios will be about the same for all n

Runing the program produces four ratios that decrease slightly from the one for n=6 to the one for n=12. Evaluating this result...

• Conclusion at this point has to be that the data aren't behaving quite as predicted.
• But the experiment should be strengthened before we really believe that conclusion, particularly in looking at more n values, especially ones larger than 12, and in repeating the measurements for each several more times.
• Decrease could be due to some overhead not reflected in the theoretical analysis that gets amortized over all the tiles the robot paints, so that for larger squares the time-per-tile decreases.

Conditionals

Chapter 5

Generic form

    if test then
        do something
    else
        do something else

(Also "if...then...else if...else if...", "switch", etc.)

What does it mean that test is "boolean?"

• Values are true/false

Logical operators?

    if ( a < b && c != 1 ) ...

• And
• Or
• Not
• Equivalence
• Implies
• Exclusive or

Truth tables

Combining logical operators (boolean algebra)

Next

Introduction to recursion

Read Section 6.1

Next Lecture