SUNY Geneseo Department of Computer Science

List Algorithms

Previous Lecture

Misc

Exam 2 will be next Thursday (April 1)

• Mainly lists, design and analysis of list algorithms
• Rules and format similar to first exam

Practice Exam on Web

Questions?

No exceptions on test

Comments are good even for face-to-face grading

List algorithms for test can be in terms of list messages

Inductions about lists are usually on length

Beware of blank lines at start of treasure hunt files

Proofs that hunts are correct

• Different case in proof for each tile color
• Induction on number of tiles in treasure hunt
  • Base case is 1 tile -- yellow
  • Don't necessarily need base cases for small treasure hunts starting with all colors
• You can add own postcondition on direction

Example List Algorithms

Mini-Assignment:

• Delete all occurrences of x

    // In some subclass of List...
    public void delete( Object x ) {
        if ( ! this.isEmpty() ) {
            if ( this.getFirst().equals( x ) ) {
                this.removeItem();
                this.delete( x );
            }
        }
        else {
            this.getRest().delete( x );
        }
    }
    // Postcondition: List contains no items
    // equal to x.

• "Equal"?
  • Same contents, form - Java: "equals"
  • Identity - Java: ==
• Does this work?
  • i.e., after "delete(x)" list contains no occurrence of x
  • Base case: empty list
    • x not in the list, postconditions hold already
    • Algorithm doesn't change anything
  • Induction hypothesis: assume for list of size k-1, "delete(x)" deletes all occurences of x
  • Show that in list of size k, "delete(x)" deletes all occurrences of x
    • Questions
      • Size of list is...
        • 0 if the list empty
        • 1 + size of tail if list is non-empty
      • Induction on # of x's in list?
        • Doesn't correspond as well to recursion in algorithm
    • Consider k-item list
    • If head of k-item list = x
      • Removes head
      • Recursively deletes from k-1 remaining elements
        • (OK by induction hyp)
    • If head <> x
      • Recursively deletes from k-1 item tail of list
        • (OK by induction hyp)
      • Leaves head where it was
• How quickly?
  • Count List messages
  • Depends on how long list is
    • f(n) = 1 if n = 0
    • f(n) = 3 + f(n-1) if n > 0
  • Theorem (exercise in Chapter 7)
    • Recurrences of the form
      • f(n) = c if n =0
      • f(n) = k + f(n-1) if n > 0
    • Have closed forms
      • f(n) = kn + c
  • Aha! for delete f(n) = 3n + 1
    • = Theta(n)

List Subclasses

Look at how removeItem works

Look at how addItem works (end of section 11.4)

Read Section 11.5.1

Next Lecture