We would like to thank Dr. Leslie Foster for contributing the "Pascal Triangle" debugging exercise.
Testing in isolation is called unit testing. It requires a test harness, that is, a function main() that calls your new function with parameters obtained from 1) user input, 2) a file or 3) a function that generates parameter values.
Write two test harnesses for the following function. The first test harness takes test values from prompted user input. The second test harness generates test cases randomly.
public class FindFirst { /** * Search a string for a substring * @param s the string to look in * @param sub the string to look for * @return if found, the integer position of sub in s else, -1 */ public static int findFirst(String s, String sub) { int i = 0; while (sub.length() + i <= s.length()) { if(s.substring(i, i + sub.length()).equals(sub)) return i; else i++; } return -1; } public static void main(String[] args) { String searchFor; String searchIn; boolean done = false; while (!done) { /* Your work goes here (get test cases consisting of two strings for findFirst()) */ } } }
When generating test cases randomly, be sure to include both positive and negative tests. That is, use 1) a random substring taken from the teststring and 2) some other random string.
Hint: We have no function to generate a completely random string, but you can write one! Make a string of the 26 lowercase letters, then extract single-character length substrings from it at positions generated by generator.nextInt(26) and concatenate them. /* your program here */
Did you think of boundary cases? What would be boundary cases in this example?
/** * Searches for last occurrence of one string in another * @param s the string to look in * @param sub the string to look for * @return if found, the integer position of sub in s else, -1 */ public static int findLast(String s, String sub) { int n = s.length; while (sub.length() <= s.length()) { if(s.substring(s.length() - 2 - sub.length(), s.length() - 2).equals(sub)) return n - s.length(); else s = s.substring(0, s.length() - 2); } return -1; }
Did one of your test cases catch it? Which?
/* Simplified calculator to perform two variable arithmetic */ public static void main(String[] args) { ConsoleReader console = new ConsoleReader(System.in); System.out.println("Enter the first argument (e.g. 2):"); double left = console.readDouble(); System.out.println("Enter the operator (+ - * /):"); String op = console.readLine(); System.out.println("Enter the second argument (e.g. 3):"); double right = console.readDouble(); double answer = 0; if (op.equals("+")) { answer = left + right; } else if (op.equals("-")) { answer = left - right; } else if (op.equals("*")) { answer = left * right; } else if (op.equals("/") { if (right != 0) { answer = left / right; } else { System.out.println("Divide by 0"); return; } } else { System.out.println(op + " is an unknown operation."); return; } System.out.println(left + " " + op + " " + right + " = " + answer);; }
Compile and run the program, then enter the test cases that you supplied. Does each branch work as expected ?
/** * Compute an integral power of a number * @param a the number to be raised to an integral power * @param n the power to which it is to be raised * @return a to the nth power */ public static double power(double a, int n) { double r = 1; double b = a; int i = n; while (i > 0) { if(i % 2 == 0) /* n is even */ { b = b * b; i = i /2; } else /* n is odd */ { r = r * b; i--; } } return r; }
/** * Compute a Fibonacci number * @param n an integer * @return the nth Fibonacci number */ public static long fibonacci(int n) { return (long)(Math.pow((1 + Math.sqrt(5)) / 2, n) / Math.sqrt(5) + 0.5); } public static void main(String[] args) { ConsoleReader console = new ConsoleReader(System.in); System.out.println("Enter the number of the Fibonacci number to be computed:"); int fibNumber = console.readInt(); /* your work goes here */ }
public static void main(String[] args) { ConsoleReader console = new ConsoleReader(System.in); double answer = 0; System.out.println("Enter the number to be raised to a power:"); double a = console.readDouble(); System.out.println("Enter the power to which " + a + " is to be raised:"); int n = console.readInt(); System.out.println("Before call to power(a,n), a= " + a + " n= " + n + " and answer = " + answer); answer = power(a, n); System.out.println("After call to power(a,n), a= " + a + " n= " + n + " and answer = " + answer); }
public class Pastri { /** * skip n spaces on a line * @param n - the number of spaces to skip */ public static void skip(int n) { int i; /* a counter */ for (i = 0; i <= n; i++ ) System.out.print(" "); } /** * calculate n factorial * @param n calculate the factorial of n * @return n! */ public static int factorial(int n) { int product; /* accumulator for the running product */ int i; /* a counter */ product = 1; for (i = 1; i <= n; i++) { product = product + i ; } return product; } /** * calculate the number of combinations of n things taken * k at a time (n choose k) * @param n the number of items to choose from * @param k the number of items choosen * @return n choose k */ public static int combination(int n, int k) { int comb = factorial(n) / factorial(k) * factorial(n-k); return comb; } public static void main(String[] args) { ConsoleReader console = new ConsoleReader(System.in); int nrows; /* the number of rows to print */ int n; /* a counter for the current row */ int k; /* a counter for the current column */ int comb; /* the number of combinations */ int spacesToSkip = 36; /* spaces to skip at the beginning of each row */ System.out.println("Enter the number of rows (<=13) in Pascal's triangle:"); nrows = console.readInt(); System.out.print("\n\n\n"); /* print the title * / System.out.println("THE FIRST " + nrows + "ROWS OF PASCAL'S TRIANGLE"); / * start a loop over the number of rows */ for (n = 0; n < nrows; n++) { skip(spacesToSkip); /* space to make a triangle */ spacesToSkip = spacesToSkip - 2; for (k = 0; k <= n; k++) { comb = combination(n,k); String out = " " + comb; // pad to a length of 4 System.out.print(out.substring(out.length() - 4)); } System.out.println(); n++; } } }
The program's purpose is to display Pascal's Triangle, a sequence of integers that arises in numerous areas of math and computer science, especially combinatorics and probability. When completed, the program's output should be:
Enter the number of rows (<= 13) in Pascal's Triangle. 5 THE FIRST 5 ROWS OF PASCAL's TRIANGLE 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
The values themselves are computed by the formula C(n, k) = n! / ( k! (n-k)!), which is called a combination. n! denotes a factorial, that is, the product n(n-1)(n-2)...(2)(1). The combinations can be interpreted as the number of ways to choose k elements from a collection containing n elements. When described, it is customary to say "n choose k", for instance '4 choose 3 is 4' ".
If 4 objects are numbered 1 through 4, how many ways can you select 2 of them ? Show all the possible pairings here. Then compute C(4, 2) by using the formula.. Does it match the number of selections?
As you will discover with the help of your debugger, the program to compute Pascal's triangle has some mistakes. Each provides an opportunity to learn a debugging concept in context of it's use.
nrows = console.readInt();
That is strange. The program is supposed to print three newlines, then the title. Let's find out why the title doesn't appear.
n: 2 k: 0
What value does product have in the debug window?
product = product + i;
product = product * i;
What happens?
n: 3 k: 1
comb = factorial(n) / factorial(k) * factorial(n-k) ;
comb = factorial(n) / (factorial(k) * factorial(n-k)) ;
They should now. Exit, saving any files you might wish to keep.