SUNY Geneseo Department of Computer Science

Correctness of List Algorithms, Part 2

Previous Lecture

Misc

CS Dept. Halloween party

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

Questions?

Extended list lab, recurrence relation for everyOtherItem

• Typically something like this (exact constants are made up)
  • f(n) = 6 if n = 0
  • f(n) = 4 if n = 1
  • f(n) = 7 + f(n-2) if n > 1
• For even n: 6, 7+6, 7+7+6, ...
• Odd n: 4, 7+4, 7+7+4, ....
• Give separate closed forms for even & odd

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
      • Obviously x is in the list, search should return true
      • Algorithm does return true because the "this.first().equals(x)" succeeds
    • First item <> x
      • Algorithm recursively searches rest of list
      • Which has k-1 items
      • So induction hypothesis applies,
      • i.e., recursion returns true if x is in rest of list, returns false if x not in rest of list
      • This is the correct answer for whole list because, since x isn't the first item, x is in that list iff x is in the tail
  • Mini-assignment was to flesh out "..." in Proof from Wednesday

Delete: result contains no occurrences of x

• Induction on length of list
• Base case, list is empty, can't contain x to begin with, so returning original list is fine
  • "this.isEmpty" succeeds and delete returns original list
• Induction hypothesis: assume deleting x from list of k-1 >= 0 items returns a list w/ no occurrences of x
• Show that delete in a list of k items returns list w/ no occurrences of x
  • delete executes "else" of outer conditional
  • Two possibilities:
    • First item = x
      • Recursively looks for x in rest of list
      • Recursion returns a list w/ no occurrences of x, by induction hypothesis
      • That result is returned, satisfying postcondition
    • First item <> x
      • Result contains first item, <> x, and a list made by recursively deleting x from tail (length k-1), which list has no x's by induction hypothesis

Devil's advocate: "better" delete

    delete( x )
        return new DataList()

• Postcondition for delete is really that result contains all items from original list not equal to x, no occurrences of x, and nothing not in original list

The Problem with Searching Lists

Theta(n) search time is really pretty bad in a big data set

Can we devise a data structure that supports faster searches?

Next Lecture