Debugging

The following portion of the lab is designed to have you practice some of the basics of debugging. Make a copy of the file \\Dragon\cls_mcdowell\CS 420\debug\pastri.cpp.

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
                

Entries in Pascal's triangle are indexed by integers. n is the number of the row and k is the position from the leftmost member of the row. The indexes in both directions start at zero (0), so in the fifth row listed above, C(4,0) = 1, C(4,1) = 4, and so on.

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 its use.

1. Run/Debug
   • Run the program in the debugger and enter 5 for input (the number of rows for the program to display)

     What output is displayed?

2. Step over / inspect
   • Restart the debugger.
   • Now use the Step Over command several times, until the active line is

     cin >> nrows;
     

   • Select Step Over again

     The program is now expecting keyboard input because the cin >> nrows line is being executed.

   • Type 5 (followed by the Enter key) for the input.

     On what line is the cursor positioned now ?

     What is the value of nrows?

3. More stepping
   • Select Step Over twice
   • Look at the output for Pascal's triangle.

     Does the output have the title:

     TABLE 1: THE FIRST 5 ROWS OF PASCAL'S TRIANGLE
     That is strange. The program is supposed to print three newlines, then the title. Let's find out why the title doesn't appear.

   • Select Kill to end the current run of the program, and then restart the debugger.
   • Select Step Over until you reach the line prompting for input.
   • Enter 5 for nrows
   • Select Step Over one more time. This should skip over the line
     cout << "\n\n\n";

   What line are you on now?

   • Notice that you skipped over the line
     cout << "THE FIRST " << nrows << " ROWS OF PASCAL'S TRIANGLE\n\n";
     The reason is that two delimiters for comments had extra spaces in them.
   • Change the line
     /* print the title * /
     into
     /* print the title */
     and the line
     / * start a loop over the number of rows */
     into
     /* start a loop over the number of rows */

   When you changed the positioning of the comment delimiters, did any changes occur to the commented text?

4. Inspecting variables
   • Recompile your program to incorporate your changes and then restart the debugger.
   • Select Run to run the program.
   • Enter 5 for the number of rows. (Use 5 for input for all the runs until part 11, below).

   Does the title now show up on the screen?

   How many rows of Pascal's triangle are displayed?

   • To find out why there are not five rows, return to the source code by pressing enter.
   • Restart the debugger.
   • Select Step Over until you reach the line
     skip(spaces_to_skip); /* space to make a triangle */

   What are the values of n and k?

   • Keep selecting Step Over until you are again at the line
     skip(spaces_to_skip); /* space to make a triangle */

   What are the values of n and k?

   • Keep selecting Step Over until you exit the for loops and arrive at the line
     return 0;

   Now what are the values of n and k?

   • View the program output. Notice that there are only three rows in the triangle. This is because the n values listed above went from 0 to 2 to 4 to 6. That is, the loop index i should have been increased by one each time, not two.
   • Change the line of code
     for (n = 0; n < nrows; n = n + 2)
     to be
     for (n = 0; n < nrows; n++)
   • Recompile
   • Select Run and input 5 to the program where prompted. You should now have five rows in the triangle.

5. Step into
   • The entries in the triangle are still incorrect. To see one reason why, restart the debugger and press Step Over quite a few times, until the variable values reach:

        n: 2
        k: 0
     

     You should be at line
     comb = combination(n, k);
   • Press Step Into, to get to the line
     int combination = factorial(n) / factorial(k) * factorial(n-k);
     Notice that Step Into goes into each function as it is executed. Using Step Over always steps over the next function to the next line of code in the current procedure.
   • Press Step Into again. You should be at the line
     int product; /* accumulator for the running product */
     in the function factorial(n)
   • What value does n have? If it is not 2, press Step Out to step out of this call to factorial and then Step In to the next call to factorial.
   • Now press Step Over until you are at the line
     return product;

   What value does n have in the window? (Note that k is undefined in the watch window since k is not active in the function factorial.

   Is the value of product equal to n! (n factorial)?

   • The reason that the value of product is incorrect is that the line
     product = product + i;
     should be
     product = product * i;
   • Press Kill to end the debugging session.
   • Make the above change in your editor.
   • Recompile
   • Run the program again with input of 5. Oh no! the triangle is still wrong!

6. Setting breakpoints

   It is tedious to have to keep stepping to get inside a program. A more efficient way is to set a breakpoint at a line of interest. Then the program runs at full speed until a breakpoint is reached.

   • Restart the debugger again.
   • Add a breakpoint at the line
     comb = combination(n,k) ;
   • Select Run until the program stops at the breakpoint.
   • Repeat selecting Run until the watch window displays

        n: 3
        k: 1
     

   • Then Step Into once
   • and then Step Over until you are at the line
     return comb;

   What is the value listed for comb?

   • The true value for the combination of 3 things taken 1 at a time is 3! / 1!·2! = 6 / 2 = 3. So, the above value of comb is wrong.
   • Something must be wrong with our combination calculation. In fact, the programmer has omitted parentheses in the denominator for the line
     comb = factorial(n) / factorial(k) * factorial(n-k) ;
   Change the line to be:
   comb = factorial(n) / (factorial(k) * factorial(n-k)) ;
   • Recompile and run the program again.

     Is your Pascal's Triangle correct (for nrows = 5)?

7. Finally
   • Select the line comb = combination(n,k) ;
   • Select Toggle Breakpoint .
   • Select Run

   Do the results look OK when you input 13 for the number of rows?

   They should now. Print the final version of pastri.cpp to hand in.

Unit Testing

Testing a function for run time errors in context of an ongoing project is always difficult. The source of an error may well be obscured by other functions, there could be more than one error, it might arise under unusual circumstances or even appear to go away. Testing a new function in isolation, before adding it to a project gives you an excellent opportunity to locate errors before they become lost in a broken project.

Testing in isolation is called unit testing. It requires a test stub, 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 a test stub for the following two functions. Be sure to include positive, negative, and boundary test cases, and to provide complete coverage of each instruction in the functions.

int find_first(string s, string sub)
/* PURPOSE:   Search a string for a substring
   RECEIVES:  sub - the string to look for
              s - the string to look in
   RETURNS:   if found, the integer position of sub in s
              else, -1 
 */

{  int i = 0; 

   while (sub.length() + i <= s.length())
   {  if(s.substr(i, sub.length()) == sub)
         return i;
      else  
         i++;
   }
   return -1;
}

int find_last(string s, string sub)
/* PURPOSE:  Searches for last occurrence of one string in another
   RECEIVES: s - the string to search in
             sub - the string to search for
   RETURNS:  if found, the integer position of sub in s
             else, 0   
 */   
{  string save_s = s; 

   while (sub.length() <= s.length())
   {  if(s.substr((s.length() - sub.length()), sub.length()) == sub)
         return save_s.length() - s.length();
      else  
         s = s.substr(0, s.length() - 2 );
   }
   return 0;
}

The function find_last contains errors. Did your test cases catch them?

Fix the errors. Once find_last is running correctly, print the correct version of find_last and the test stub to hand in.

Turn in copies of your final pastri.cpp file, your corrected find_last function, and the test stub for the find_first and find_last functions.

^*This lab is based on the lab by Cay Horstmann and Geof Pawlicki to accompany Chapter 7 of Computing Concepts with C++ Essentials by Cay Horstman, John Wiley & Sons, Inc., 1999. Dr. Leslie Foster contributed the "Pascal Triangle" debugging exercise.