SUNY Geneseo Department of Computer Science

Overview of the Scientific Method

Previous Lecture

Misc

Hand out Lab 2

Next Thursday (1/29) I'm out of town

• Attend "town meeting" on plagiarism for extra credit instead of coming to regular class
• 12:45 - 1:50, Milne 104

CS learning center is open

Questions?

Instrumentation code not measuring itself?

    // initialize an array:
    //	Measure how many assignments to array
    //	Measure time
    long start = System.currentTimeMillis();
    int count = 0;
    for ( i = 0; i < a.length; i++ ) {
        a[i] = 0;
        count = count + 1;
    }
    System.out.println( count );
    long end = System.currentTimeMillis();

• Orange instrumentation code is also measuring red instrumentation code

Controls

    long start = System.currentTimeMillis();
    for ( i = 0; i < a.length; i++ ) {
        a[i] = 0;
    }
    long end = System.currentTimeMillis();
    ...
    long controlStart = System.currentTimeMillis();
    long controlEnd = System.currentTimeMillis();

Garbage collection?

• Tends to happen after you destroy objects
• Bad because it takes time
• Don't do this:

        for ( int i = 0; i < n; i++ ) {
            Robot r = new Robot();
            .... currentTimeMillis();
            r.move();
            ... currentTimeMIllis();
        }

• Better (this is better with respect to gabage collection, and it shows completely how one might average all the individual times):

        Robot r = new Robot();
        long total = 0;
        for ( int i = 0; i < n; i++ ) {
            long start = System.currentTimeMillis();
            r.move();
            long end = System.currentTimeMIllis();
            total = total + (end-start);
        }
        .... total / n ...

Step counts do act well as surrogates for time

Northwest Corner Algorithm

Look at Finished Algorithm

Reading Summary

Sections 4.1 - 4.6

Scientific method

• Experiment
  • Hypothesis
  • Predictions (make before experimenting)
  • Procedure
    • Dependent vs independent variables
    • Accuracy vs precision vs range
  • Data
  • Data analysis
  • Conclusions support rather than prove hypothesis

Scientific theory

Instrumentation and timing

Ensuring accuracy in computer timing

• Avoid multitasking
• Disconnect from net
• Avoid garbage collection
• Avoid I/O

Errors

• Random error = random
  • Can't prevent, but can control
• Systematic error = program-wide
  • Can't control, can prevent
• Relative error = error as percentage of nominal measurement
• Standard error = statistic that measures error in average

True values (?)

• There is no such thing

Error control/estimation

• Discard outliers
• Average many measurements
• Standard deviation to estimate error

Try an Experiment

Hypothesis: spinning ball ties up my computer for ten minutes at a time

Procedure: Time the ball several times

Data: 70 sec, 68 sec

Analysis: average times

• 69 sec

Conclusion: hypothesis is pretty far-fetched

Next

Start looking at methods of inquiry in connection with actually designing and coding algorithms

Conditionals (if-then, if-then-else, switch)

Read Sections 5.1 - 5.5

Next Lecture