Testing of Programs (Jan 23)

Added notes about the tests we did in class, and question 12 regarding loop invariants.

Warmup exercises

I would recommend reading the lecture notes on Testing first (#5-6) first. Most of the questions in the warmup exercises ask for definitions of terms; you can find most of these in the lecture notes.

The lecture notes don't seem to cover Syntax, Runtime, and Logic Errors, but these concepts aren't very difficult.

Syntax Error: This has to do with the "grammar" of the language you are programming in. These are usually the errors you see when you try to compile your program. You cannot run your program until you fix these errors.

Runtime Error: These errors occur after you start your program, hence the name "runtime". Most commonly they result from asking the computer to do something it isn't able to. For example, you may be dividing by zero, or accessing an out of bounds index for an array. While some compilers can predict/detect some of these errors, you will still encounter these very frequently. For example, you may be using a variable, or you might be relying on some resource outside of your control (like a network). Thankfully, these errors tend to be easier to trace IF you have organized code and good documentation.

Since Runtime Errors often cause your program to halt or crash, you want a way to handle them elegantly. We usually catch and handle the Exceptions which are raised/thrown by the computer. You can read more about Runtime Errors and Exception Handling in this other tutorial, linked in the course website.

Logic Error: Perhaps the most difficult to detect and fix, these errors often go unnoticed because the computer does not provide any hints. The syntax is correct and there are no runtime errors, but the output is not what you would expect. Examples include incorrect implementation of math or algorithms, incorrect branching in conditionals, using the wrong functions, etc. If you did CPSC 355, you probably remember trying to do the multiplier/product assignment, or the last assignment with exponents, and getting the wrong output displayed.

[T03WarmupExercises.pdf][83KB]

Black-box testing vs white-box testing (questions 10, 11a)

We designed a bunch of black-box tests, but didn't go over white-box tests in much detail. Because our code was so simple, our black-box tests actually accomplished most of what we want through white-box testing as well.

Black-box testing looks at typical+boundary cases, and tests both valid and invalid input. This is done without any knowledge of the code or implementation.
White-box testing tries to test every line of code and every execution path. For conditionals, test all the branches. For loops, test the loop conditions, and test different numbers of loop executions if possible.

In our case, the above goals of white-box testing are satisfied through our black-box tests. Testing both distinct and indistinct entries will test the conditional and the loop exit conditions, while testing boundary cases also tests the loop conditions. In the black-box tests shown in class, we used arrays [], [0], [1, 2, 1], [1, 1, 2, 2, 3], and a few others for input. These resulted in different numbers of loop executions.

Black-box testing and white-box testing are the two types of "Dynamic Testing". In question 11b, we did "Static Testing", to quickly look for mistakes in the code, by hand, without execution of the code (hence "static").

Static Testing (question 11b)

There were two ways to identify the 4 errors.

  1. Given the correct loop invariants, you can identify many hints. Loop invariants almost always include a statement regarding the loop condition by definition. According to lecture notes, loop invariants are true directly after loop conditions are satisfied, before the loop body is executed.

    Since 1 <= i, we know i starts from 1. (this is already correct)
    Since i < A.length, we know the loop condition must be the same. Otherwise the loop invariant would be incorrect on the very last loop iteration.
    Since 0 <= j, we know j starts from 0.
    Since j <= i, we know the loop condition must be the same.

    Finally, A[j] = A[i] is just a syntax error, and should be A[j] == A[i] in Java. A single "=" is used for assignment, like assigning values to variables. 


  2. Without using the loop invariants, you can still reason through this problem.

    Incorrect boundaries of arrays is one of the most common problems you will face early on in programming. Given how short this program is, and knowing some errors exist, it is almost certain there are errors in the loop conditions.

    If you understood the algorithm in 11a, then you should know that the outer loop iterates through the array, introducing one number at a time to check for distinctness. The reason i starts at 1 and not 0, is because we compare A[i] with all the entries before it. If i = 3, we compare A[3] with A[0], A[1], and A[2]. If i = 1, we just compare A[1] with A[0]. But if i = 0, there are no numbers before it, and the inner loop (which makes up the loop body of the outer loop) will not execute at all.

    We know i < A.length, rather than i <= A.length, because if i = A.length, then accessing A[A.length] will result in an IndexOutOfBoundsException. In Java, the indices start from 0, and end at A.length-1.

    From above, we know that we need to compare all entries A[j] with A[i], such that j < i. This of course includes the first entry of array A, hence j = 0 (j starts at 0) instead of j = 1.

    Using what we know about the algorithm, we know j should never equal i. If j = i, then A[j] = A[i], and comparing A[j] with A[i] will always result in a "duplicate". The algorithm will always return false. Instead of j <= i, it should be j < i.

    Finally, A[j] = A[i] is a syntax error, and should be A[j] == A[i].

Loop invariants (question 12)

To understand the purpose of the loop invariants, you really have to undertand what is happening in the algorithm.

Given the above index of size 5, you can see how the algorithm does each comparison.

Note that i (green) starts at 1, and is always less than A.length (n = 5). This give you the first loop invariant for the outer loop: 1 ≤ i < A.length

Similarly, j (red) starts at 0, and is always less than i. Since we also know that i < A.length, we can combine these to get the first loop invariant for the inner loop: 0 ≤ j < i < A.length

Outer loop invariant b states that A[r] is not equal to A[s] for all integers r and s such that 0 ≤ r < s < i. To paraphrase this, every entry with index less than i is unique. We have to use two new variables, r and s, because r cannot equal s. The loop invariant says r < s, rather than r ≤ s. If we were to let r = s, then A[r] = A[s], and we would be comparing the same number with itself.

You can see that at the beginning of outer loop #2 when i = 2, we have just shown A[0] and A[1] to be unique. At the start of outer loop #3 when i = 3, we know A[2] to be unique, and we already knew A[0] and A[1] to be unique.

During each outer loop, we execute the inner loop to compare the current index i with all the numbers before it (index j).

Now we can answer question 12b: why are inner loop invariants b) and c) important?

Recall the process to prove a loop invariant by induction: given a base case i, assume there will be an i+1st execution. With this assumption, we know that A[j] ≠ A[i]. If A[j] did infact equal A[i], the algorithm would have already returned false and the outer loop would not execute the i+1st time.

Here's what we know at the end of the last execution of the inner loop, BEFORE the i+1st execution of the outer loop:

  1. A[r] is not equal to A[s] for all integers r and s such that 0 ≤ r < s < i   (loop invariant b)
  2. A[r] is not equal to A[i] for every integer r such that 0 ≤ r < j   (loop invariant c)
  3. A[j] ≠ A[i]   (assume i+1st execution, then algorithm cannot return false, therefore A[j] ≠ A[0])
  4. Combine points 2 and 3, A[r] is not equal to A[i] for every integer r such that 0 ≤ r ≤ j.
  5. Since it's the last inner loop execution, the loop condition tells us that j = i-1. Combined with point 4, we can say that A[r] is not equal to A[i] for every integer r such that 0 ≤ r < i

Almost there! Combine point 5 with loop invariant b. If A[r] is not equal to A[s] for all integers r and s such that 0 ≤ r < s < i, and A[r] is not equal to A[s] when s = i, then we know A[r] is not equal to A[s] for all integers r and s such that 0 ≤ r < s=i < i+1. This shows that outer loop invariant b will hold for the 1+st execution.

JUnit tests

Note: The attached source file is not corrected yet. As part of the in-clsas exercise, you have to find and fix the 4 errors.

Download tests for Distinct Entries algorithm: [T03Testing.zip](5KB)

  1. Open Eclipse.
  2. Select File > Import.
  3. Select General > Projects from Folder or Archive.
  4. On the right-top corner, select Archive...
  5. Find and select the .zip file you downloaded.
  6. In the new list, ONLY select the one with "Eclipse Project" under "Import as"
  7. Click Finish. Project should show up in Package Manager now.

The tutorial #3 page on the course website links to this tutorial for JUnit. It shows you how to use JUnit in command line, so you can test your assignments. It also links to more resources which may be helpful; reference as needed.