Contents [0/21]

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

 Video [1/21]

In two parts

 Open Playlist
```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
```

 What does this function do? [2/21]

 ``` 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? [3/21]

 ``` 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? [4/21]

 ``` 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? [5/21]

 ``` 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! [6/21]

 ``` 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 [7/21]

 ``` 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.

• What was the output supposed to be?

 Automatic Testing [8/21]

 ``` 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 [9/21]

 ``` 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 [10/21]

 ``` 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

 Generalizing [11/21]

 ``` 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 [12/21]

 ``` 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

 ``` 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

• 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]

 ``` 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

• 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]

 ``` 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 [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]

 ``` 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[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]

 ``` 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 [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