SUNY Geneseo Department of Computer Science

List Algorithms

Previous Lecture

Misc

Hand out Lab 8

Questions?

List Implementation

Sections 11.3 and 11.4

Basic constructor, creates empty list

getFirst produces value

removeItem produces side-effect

getRest, maybe most important

Methods built from primitive operations often have 3-case structure:

• Case 1: empty list
• Case 2: first item is what you want
• Case 3: keep looking in tail of list

Java syntax question:

• Bodies of "if", loops, are always single statements

    while ( i < 10 )
        i = i + 1;

• vs

    while ( i < 10 )
        System.out.println( i );
        i = i + 1;

• {...} groups statements into a single "super-statement" aka block

Operations that might be useful

• Constructor
• getFirst
• getRest
• removeItem
• getAndRemove
• isEmpty
• addItem
• setFirst
• setRest

List Algorithms

Given a list of numbers, return the first odd one (or 0 if the list contains no odd numbers)

    // In class List...
    // Precondition: list contains only integers
    int firstOdd()
        if ! this.isEmpty()
            if this.getFirst() % 2 != 0
                return this.getFirst()
            else
                return this.getRest().firstOdd()
        else
            return 0

• Is this correct?
  • Induction on...
    • Position of 1st odd number?
    • * Length of list?
  • Proof for base case
    • No odd number?
    • Odd number at end of list?
    • Odd number at beginning of list?
    • * Empty list?
  • Algorithm is correct for an empty list because...
    • Empty list contains no odd numbers, so algorithm should return 0, and does
  • Induction hypothesis: assume if length is k-1, then firstOdd returns first odd number in list or 0
  • Induction step, show if length is k, then firstOdd returns first odd number in list or 0
    • If first element is odd, it gets returned, and is clearly first odd element
    • Otherwise it returns first odd element in tail of list (because recursion on "this.getRest()" is working on k-1 elements, does so correctly by induction hypothesis), which must be first odd in whole list
• How fast is it (in terms of n items in list)?
  • Best vs worst case
  • Mini-assignment: derive rigorously Θ(n) worst-case execution time

Next

Subclasses of List

Read Section 11.5 through subsection 11.5.2

Next Lecture