Topics to discuss

• Predicates * CHECK
• Anonymous procedures / lambdas CHECk
• Anonymous inner classes CHECK
• Big O notation
• Loop invariants
• Tell us about the experience of designing an API
• Wouldn't we be better off doing a hack-a-thon rather than your exam?

Can you give us sample grades? Yes. After the first exam.

Predicates

In Scheme, a predicate is a function that returns true or false. even? exact? list? color? = equal? eq?

In Java, a Predicate is an object that (1) implements the Predicate interface and (2) includes a method test(T val).

Predicate is really java.util.function.Predicate and it's a generic interface.

We have three ways of making these kinds of objects.

• Make a class that implements the interface, instantiate that class.
• Make an object using anonymous inner classes
• Use a lambda expression

Examples

    public class Even
        implements Predicate<Integer>
    {
      public boolean test(Integer val)
      {
        return (val % 2) == 0;
      } // test(Integer)
    } // class Even

Somewhere else in my code ...

    Predicate<Integer> even = new Even();

Anonymous inner classes

    Predicate<Integer> even = new Predicate<Integer>() {
      public boolean test(Integer val)
      {
        return (val % 2) == 0;
      } // test(Integer)
    };

Anonymous procedures

    Predicate<Integer> even = (val) -> (val % 2) == 0;
    Predicate<Integer> even = (val) -> { return (val % 2) == 0; }

Anonymous Procedures

• Effectively shorthand for the longer class (we can pretend that it's "syntactic sugar")

Let's look at a more complex example

    @FunctionalInterface
    public interface ArrayManipulator<T>
    {
      public T manipulate(T[] vals, int i);
    } // ArrayManipulator

    ArrayManipulator<Integer> albert = (larray, x) -> { return larray[x]; }

Big O Notation

What is the idea of Big O?

• As we use it: Model the shape of the curve that relates running time to input size.
  
  • Input size: Number of elements in a list or array, characters in a string, or maybe even just an integer
  • "Shape of the curve"
    • Horizontal line - O(1)
    • Logarithmic O(logn)
    • Linear (but not horizontal) The running time is directly proportional to the input size - O(n) a*n + b
    • O(nlogn)
    • Quadratic O(n^2)

How do you do the analysis?

• Count steps!

  sum = 0;
  int len = lst.length();
  for (i = 0; i < len; i++)
    {
      sum += lst.get(i);
    } // for
  return sum
  

• Count the repetitions: n

• Count the cost of each: lst.get could take as many as n steps.
• Multiply: O(n^2)

Let's suppose we just tried to count each time through

1 + 2 + 3 + 4 + ... + n = n(n+1)/2 = n^2/2 + 1/2 is in O(n^2)