SUNY Geneseo Department of Computer Science

Overview of Experimentation

Return to List of Lectures

Questions?

Product of 2 evens divisible by 4 f/ problem set?

• Think of even number as 2i, for integer i
• Two even numbers would be 2i and 2j
• Their product is 2i * 2j = 2 * 2 * i * j = 4 ij
• 4ij is a multiple of 4, QED

Third question: 0 is even

The Scientific Method and Algorithms

Sections 4.1 through 4.7

• Role of experiments
• Theory, hypothesis, predictions
• Independent variable = cause, established by experimenter
• Dependent variable = effect, result measured by experimenter
• Use appropriate instruments
  • Accuracy, precision, range
• Multiple measurements, repeat many times
  • Use average as "real" value
  • Beware outliers
• Experimental error
  • Systematic error
  • Random error
• Measuring time on computers
• Data
• Data analysis
• Conclusion

Example

• A very inefficient way to compute 2ⁿ. (See program)
  • Time to compute 2ⁿ is roughly twice the time to compute 2^n-1
  • i.e., for each unit increase in n, time doubles
  • i.e., time to compute 2ⁿ ought to be more or less proportional to 2ⁿ itself
• Hypothesis...?
  • Question: Does pushing mouse around really change running time?
  • Formal Hypothesis: This program will take the same time to run while cursor is being pushed around as while cursor is not being pushed around
• Design
  • Add timing code to measure program
  • Time exponentiation and printing, not input
  • Run program without moving mouse
  • Then run on same input with moving mouse
  • Note difference
  • Repeat above several times
• Results in nanoseconds from 2 repetitions computing 2²⁰ (what we had time for, more would be necessary for a really compelling experiment)

• Exponentiation time does seem to increase if the mouse is moving, so this experiment refutes our hypothesis.

Next

Tools for reasoning about and working with conditionals

Read sections 5.1 through 5.5