CSC300 / CSC402: Thinking about loops

Contents [0/20]

What does this function do? [1/20]
How do you know? [2/20]
How do you know? [3/20]
How do you know? [4/20]
You don't need the code! [5/20]
Manual Testing [6/20]
Automatic Testing [7/20]
Using an array of length 3 [8/20]
Using a loop [9/20]
Generalizing [10/20]
Loop invariant [11/20]
A bad solution [12/20]
Exceptions [13/20]
Designing loops from scratch [14/20]
Solution with while loop [15/20]
General rules for desiging loops [16/20]
Another way to compute max [17/20]
Another way to compute max [18/20]
Using a timer [19/20]
Conclusions [20/20]

(Click here for one slide per page)


What does this function do? [1/20]

01
02
03
04
05
06
07
08
09
  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? [2/20]

01
02
03
04
05
06
07
08
09
  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? [3/20]

01
02
03
04
05
06
07
08
09
  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? [4/20]

01
02
03
04
05
06
07
08
09
  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! [5/20]

01
02
03
04
05
06
07
08
09
  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 [6/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
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.

Automatic Testing [7/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
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 [8/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
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 [9/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 [10/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 [11/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 [12/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

Exceptions [13/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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

Designing loops from scratch [14/20]

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

Solution with while loop [15/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 [16/20]

Another way to compute max [17/20]

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 [18/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 [19/20]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 [20/20]

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

Loop invariants are useful

Performance matters