CSC300: Thinking about loops

00:00 Logical thinking
03:45 Testing
10:11 Using an array as the parameter
11:49 Looping over the array
13:22 Three is a magic number: use array length
14:58 Understanding the correctness of loops
17:24 Invariants
18:22 Exceptions and debugging
19:56 Zero is a magic number: throw an exception
22:41 Testing exceptions

Open Playlist

00:00 Designing loops: start in the middle
03:34 Designing loops: how to stop
04:09 Designing loops: how to start
04:52 You don't always start at zero!
05:41 Designing loops: corner cases
09:06 Another solution
15:38 Using performance to compare the solutions
19:12 Observing a linear-time algorithm
20:44 Observing a quadratic-time algorithm

What does this function do? [2/21]

  public static int f (int x, int y, int z) {
    int m = x;

    if (m < y) { m = y; }

    if (m < z) { m = z; }

    return m;
  }

How do you know? [3/21]

  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }

    if (m < z) { m = z; }

    return m;
  }

How do you know? [4/21]

  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }
    /* m == max(x,y) */
    if (m < z) { m = z; }

    return m;
  }

How do you know? [5/21]

  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }
    /* m == max(x,y) */
    if (m < z) { m = z; }
    /* m == max(x,y,z) */
    return m;
  }

You don't need the code! [6/21]

  public static int f (int x, int y, int z) {

    /* m == max(x) */

    /* m == max(x,y) */

    /* m == max(x,y,z) */
    return m;
  }

Manual Testing [7/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static int max (int x, int y, int z) {
    int m = x;
    if (m < y) { m = y; }
    if (m < z) { m = z; }
    return m;
  }
  public static void main (String[] args) { 
    StdOut.println (max(11, 21, 31));
    StdOut.println (max(11, 31, 21));
    StdOut.println (max(31, 11, 21));
  }
}

Manual testing does not scale.

Manual testing instills fear of change.

What was the output supposed to be?

Automatic Testing [8/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static int max (int x, int y, int z) {
    int m = x;
    if (m < y) { m = z; }
    if (m < z) { m = z; }
    return m;
  }
  public static void testMax (int expected, int x, int y, int z) {
    int actual = max (x, y, z);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with arguments (%d,%d,%d)\n", expected, actual, x, y, z);
    }
  }
  public static void main (String[] args) { 
    testMax(31, 11, 21, 31);
    testMax(31, 11, 31, 21);
    testMax(31, 31, 11, 21);
    StdOut.println ("Finished tests");
  }
}

Passing tests are silent.

Failing tests print a meaningful message.

There are many frameworks for writing tests.

Using an array of length 3 [9/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    if (m < a[1]) { m = a[1]; }
    if (m < a[2]) { m = a[2]; }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    StdOut.println ("Finished tests");
  }
}

Using a loop [10/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < 3; i++) {
      if (m < a[i]) { m = a[i]; } 
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    StdOut.println ("Finished tests");
  }
}

3 is a magic number: it is completely arbitrary

Magic numbers are bad

Generalizing [11/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    StdOut.println ("Finished tests");
  }
}

How do we know it's correct?

Loop invariant [12/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      /* m == max(a[0]...a[i-1]) */
      if (m < a[i]) { m = a[i]; }
    }
    /* m == max(a[0]...a[a.length-1]) */
    return m; 
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    StdOut.println ("Finished tests");
  }
}

A loop invariant is something that is true every time, before executing the body of the loop

What about the empty array?

A bad solution [13/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { return 0; }
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    testMax(0,  new double[] { });
    StdOut.println ("Finished tests");
  }
}

0 is a magic number: it is completely arbitrary

Magic numbers are bad

Should { } and { 0 } have the same max?
For doubles, we could use Double.NEGATIVE_INFINITY instead of 0. This makes mathematical sense
But there is not always a good choice

Exceptions [14/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }    
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

Exceptions were created to solve this problem

Testing for an exception is interesting

In this case, we want the exception to occur; the test fails if it does not

Designing loops from scratch [15/21]

Usually, we design a loop from scratch, rather than adapting a solution for 3 elements

Lets try it for max

Lets work with the following example:

new double { 21, 41, 31, 51, 11 }
                         ^

Suppose our loop has already looked at the first three numbers, and we are considering the fourth

What do we need to know about the first three numbers?
What do we need to do with the fourth number to make progress?

Solution with while loop [16/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }
    double m = a[0];
    int i = 1;
    while (i < a.length) {
      if (m < a[i]) { m = a[i]; }
      i += 1;
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

General rules for desiging loops [17/21]

Pick an example, and start in the middle
- Figure out how to make one step of progress
- What did you need to have done previously in order to make progress? This tells you what variables you need
- Write the code for the body of the loop
Figure out the end of the loop
Figure out the beginning. What values do the variables need to start?
- It's not always 0
Figure out any corner cases (such as empty array)

Another way to compute max [18/21]

new double { 21, 41, 31, 51, 11 }
                         ^

Suppose we know that the first three numbers are not the max

What do we need to do with the fourth number to make progress?

Another way to compute max [19/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    for (int i=0; i < a.length; i++) {
      boolean isMax = true;
      for (int j=0; j<a.length; j++)
        if (a[j] > a[i])
          isMax = false;
      if (isMax) return a[i];
    }
    throw new IllegalArgumentException(); 
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

Are these solutions of equal quality?

Using a timer [20/21]

package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }
    double m = a[0];
    int i = 1;
    while (i < a.length) {
      if (m < a[i]) { m = a[i]; }
      i += 1;
    }
    return m;
  }

  public static double timeTrial(int N) {
    double[] a = ArrayGenerator.doubleSortedUnique(N);
    Stopwatch s = new Stopwatch();
    max (a);
    return s.elapsedTime();
  }

  private static final int MIN =         1_000;
  private static final int MAX = 1_000_000_000;
  public static void main(String[] args) {
    double prev = timeTrial(MIN);
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format("%10d %9.3f %5.1f\n", N, time, time/prev);
      prev = time;
    }
  }
}

Conclusions [21/21]

To read or write a program, we must think incrementally, in small steps

Loop invariants are useful

Performance matters

Revised: 2008/03/17 13:01