SUNY Geneseo Department of Computer Science

Correctness of List Algorithms

Previous Lecture

Misc

Hand out Lab 10

CS Dept. Halloween party

• Friday, Oct. 31, 5:00
• South 309

Questions?

Counting operations in an algorithm

• Method A that calls method B
• Count should include operations in both A and B

Reading Summary

Sections 9.2.2, 9.2.3

Asymptotic notation = way to find simpler function than actual closed form for recurrence to show how time grows

Take fastest-growing term in equation,

• f(n) = Theta( ... fastest-growing term .. )
• Means "roughly proportional"

Proportionality is all you can say about running time relative to theoretically derived times because of computer speeds

Testing asymptotic hypotheses ???

• Idea: Look for constant of proportionality between f(n) and measurements

Asymptotic List Performance

Correctness of List Algorithms

    class DataList extends List {

        DataList insert( Object x ) {
            return new DataList( x, this )
        }

        boolean search( Object x ) {
            if ( ! this.isEmpty() ) {
                if ( this.first().equals(x) ) {
                    return true
                }
                else {
                    return this.rest().search( x )
                }
            }
            else {
                return false;
            }
        }

        DataList delete ( Object x ) {
            // Postcondition: Result contains no
            // occurrences of x
            if ( this.isEmpty() ) {
                return this
            }
            else {
                if ( this.first().equals(x) )
                    return this.rest().delete( x )
                else {
                    return new DataList( this.first(), this.rest().delete( x ) )
                }
            }
        }
    }

Search: returns true if x is in the list, returns false if x is not in list

• Induction on size of list
• Base Case: empty list
  • Can't contain x
  • Therefore search should return false
  • And it does because "! this.isEmpty()" fails, causing algorithm to execute "return false"
• Induction hypothesis
  • Assume search in a list of length k-1 >= 0 (i.e., list might or might not be empty) returns true if x in list, false if x not in list
• Show search in list of length k returns true if x in list and false if x not in list
  • List of length k is definitely not empty, because k > 0
  • "! this.isEmpty()" succeeeds
  • 2 possibilities:
    • First item = x
      • ...
    • First item <> x
      • ...
  • Mini-assignment: flesh out "..." above

Next Lecture