BIG C++
Cay Horstmann & Timothy Budd

Laboratory Notebook
Chapter 8 - Debugging


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


We would like to thank Dr. Leslie Foster for contributing the "Pascal Triangle" debugging exercise.


Lab Objectives

To gain experience with


P1. Unit Tests

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

#include <iostream>
#include <string>
using namespace std;

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 main()
{  string search_for;
   string search_in;
   bool done = false;
    
   while (not done)
   {  /* 
          Your work goes here 
          (get test cases consisting of two strings for find_first())
       */ 

   }

   return 0;
}

Test harness having user input test cases.

Test harness having randomly generated test cases.

When generating test cases randomly, be sure to include both positive and negative tests.

It is of course tedious to type in lots of test data every time you find a bug in your code. How can you reduce that workload ?

Did you think of boundary cases? What would be boundary cases in this example?


R1. Finding a Bug

Now run the following function through two test procedures (manual and automatic test case generation)

#include <iostream>
#include <string>
using namespace std;

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
 */   
{

int find_last(string s, string sub)
{
   while (sub.length() <= s.length())
   {
     if(s.substr(s.length() - sub.length(), s.length()) == sub)
       return s.length() - sub.length();
     else  
       s = s.substr(0, s.length() - 1 );
   }
   return 0;
}

What is the error?

Did one of your test cases catch it ? Which ?


R2. Selecting Test Cases

Test cases should provide complete coverage of each instruction branch in your function. Every branch, for example both statement blocks in an if - else pairing, should succeed and fail at least once each.

/* PURPOSE:  Simplified calculator to perform two variable arithmetic
*/

#include <iostream>
#include <string>
using namespace std;
        
int main()
{  double left, right, answer;
   string op;

   cout << "enter an arithmetic expression of form (e.g. 2 + 3):" << "\n";
   cin >> left >> op >> right;

   if (op == "+" )
   {  answer = left + right;
   }
        
   else if (op == "-" )   
   {  answer = left - right;
   }

   else if (op == "*" )   
   {  answer = left * right;
   }
        
   else if (op == "/" )   
   {  if (right != 0)
      {   answer = left / right;
      }
      else
      {  cout << left << " / " << right << " can't be computed with a 0 denominator" << "\n";
         return 1;
      }
   }
   else
   {  cout << op << " is an unknown operation." << "\n";
      return 1;
   }
        
   cout << left << " " << op << " " << right << " = " << answer << "\n";
   return 0;
}           
     

Give a set of test cases for left, op, and right that provide complete coverage of all branches.

Compile and run the program, then enter the test cases that you supplied. Does each branch work as expected ?


P2. Test Case Evaluation

Having tested the input to a function, how can the output be validated? You can :

Let's test the power() function from page 273

double power(double a, int n)
/* PURPOSE:  Compute an integral power of a number
   RECEIVES: a - the number to be raised to an integral power
             n - the power to which it is to be raised
   RETURNS:  a to the nth power
 */   
 
{  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;
} 

Write a program that uses the reciprocal sqrt to test whether sqrt(power(x,2)) == x

If the test succeeds, how much confidence do you have that power is correct ?

Use the fact that xy = ey.log(x). Write a program that computes the power function in another way, and compares the two values.

(Extra credit) Which way is actually faster, power(double a, int n) or xy = ey.log(x)?


P3. Oracles

Use the fib function in ch12/fibloop.cpp as an oracle to test whether the following function is correct:

#include <iostream>
#include <cmath>
using namespace std;

long fibonacci(int n)
/* PURPOSE:  Compute a Fibonacci number
   RECEIVES: n - an integer
   RETURNS:  the nth Fibonacci number
*/
{  return (long)(pow((1 + sqrt(5.0)) / 2, n) / sqrt(5.0) + 0.5);
}


int main()
{  int fib_number = 0;
      
   cout << "Enter the number of the Fibonacci number to be computed : " << "\n";
   cin >> fib_number; 

   /*
      your work goes here
   */

   return 0;
}


P4. Assertions

Use assertions in the following example to signal that an improper input has occurred and to prevent the bad parameters from being utilized by the function.

#include <iostream>
#include <assert.h>
using namespace std;

int convert_to_sec(int hours, int min)
/* PURPOSE:  Compute seconds from midnight
   RECEIVES: hours - hour of a clock time (between 0 and 23)
             min - minutes of a clock time (between 0 and 59)
   RETURNS:  the number of seconds between midnight and the clock time
*/
{  /* your work here -- assert that hours and min are within input range */
   return hours * 3600 + min * 60;
}

int seconds_between(int hfrom, int mfrom, int hto, int mto)
/* PURPOSE:  Compute the number of seconds between two clock times
   RECEIVES: hfrom, mfrom - the hours and minutes of the earlier time
             hto, mto - the hours and minutes of the later time
   RETURNS:  the number of seconds between them 
{  int secs = convert_to_sec(hto, mto) - convert_to_sec(hfrom, mfrom);
   /* your work here -- assert that the from time is before the to time */
}  
int main()
{  int start_hr;
   int start_min;
   int end_hr;
   int end_min;

   cout << "Input start time: (hh mm) :" << "\n";
   cin >> start_hr >> start_min;

   cout << "Input end time: (hh mm) :" << "\n";
   cin >> end_hr >> end_min;
   
   cout << seconds_between(start_hr, start_min, end_hr, end_min) << " seconds elapsed\n";

   return 0;
}

How does your program handle

input error, ie. start > end ?

hours > 23 or minutes < 0


R3. Program Traces

A program trace is the result of print statements at known points in a program. It shows that the program has executed commands up to a certain point. For example, the following main() function documents the parameters to power(int a, int n).

 
int main()
{  double a;
   int n;
   double answer;

   cout << "Enter the number to be raised to a power; " << "\n";
   cin >> a;
   cout << "Enter the power to which " << a << " is to be raised: " << "\n";
   cin >> n;

   answer = power(a, n);

   cout << "Before call to power(a,n), a= " << a <<
      " n= " << n           << " and answer = " <<
      answer << "\n";

   cout << answer << "\n";
   return 0;
}

Add print statements to the preceeding power(int a, int n) function to document all changes to variables r, a and n. Show the resulting trace when power is called with a = 3 and n = 11.


R4. The Debugger

The following portion of the lab is designed to have you practice some of the basics of debugging. Copy the following program listing into a new file called pastri.cpp on your hard drive.


/*******************************************************************
*    PROJECT:     Lab assignment on debugging
*    FILE:        pastri.cpp
*    PURPOSE:     To compute Pascal's triangle and illustrate
*                 the use of the debugger.
*    PROGRAMMER:  Leslie Foster
*    REMARKS:     The code below is chosen to illustrate the debugger.
*                 It is neither the most efficient nor the most reliable
*                 way to solve this problem.
*************************************************************************/


#include <iostream>
#include <iomanip>
using namespace std;

/*------------------------------------------------------------------*/

void skip(int n)
/*  PURPOSE:  To skip n spaces on a line
    RECEIVES: n - the number of spaces to skip
    REMARKS:  n should be non-negative
*/
{  int i;  /* a counter */

   for (i = 0; i <= n; i++ )
      cout << " ";
}
/*------------------------------------------------------------------*/

int factorial(int n)
/*  PURPOSE:  To calculate n factorial
    RECEIVES: n - calculate the factorial of n
    RETURNS:  n factorial
    REMARKS:  n must be >= 0.  Also if n is too large overflow may result
*/
{  int  product; /*  accumulator for the running product  */
   int  i; /*  a counter  */

   product = 1;
   for (i = 1; i <= n; i++)
   {   product = product + i ;
   }
   return(product);
}

/*------------------------------------------------------------------*/

int combination(int n, int k)
/* PURPOSE:  to calculate the number of combinations of n things taken
             k at a time (n choose k)
   RECEIVES: n - the number of items to choose from
             k - the number of items choosen
   RETURNS:  n choose k
   REMARKS:  n and k must be non-negative and k <= n.  This program uses
             the formula (n choose k) = n! / ( k! * (n-k)! ).
*/
{  int comb = factorial(n) / factorial(k) * factorial(n-k);

   return comb;
}

/*------------------------------------------------------------------*/

int main(void)
{  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 spaces_to_skip; /*  spaces to skip  */

   cout << "Enter the number of rows (<=13) in Pascal's triangle: ";
   cin >> nrows;
   cout << "\n\n\n";

   /*  print the title  * /
   skip(16);
   cout << "TABLE 1: THE FIRST " << nrows << " ROWS OF PASCAL'S TRIANGLE\n\n";

   / *  start a loop over the number of rows  */
   spaces_to_skip = 36;

   for (n = 0; n < nrows; n = n + 2)
   {  skip(spaces_to_skip); /* space to make a triangle */
      spaces_to_skip = spaces_to_skip - 2;

      for (k = 0; k <= n; k++)
      {  comb = combination(n,k);
         cout << setw(4) << comb;
      }

      cout << "\n" ;
    }

    return 0;
}


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 it's use.

Compile the file

What output is displayed?

Step over / inspect

On what line is the cursor positioned now ?

What is the value for nrows shown in the dialog box?

More stepping

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.

What line are you on now?

When you changed the positioning of the comment delimiters, did any changes occur to the commented text? This depends on your development environment--describe what happened, if anything.

Watch

Does the title now show up on the screen?

How many rows of Pascal's triangle are displayed?

How many lines are now in the watch window?

What values of n and k are in the watch window? (If the watch window isn't present select View Watch

What are the values of n and k?

Now what are the values of n and k?

Step into

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.

What value does product have in the inspect window?

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.

What is the value listed for comb?

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

Finally

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

They should now. Exit, saving any files you might wish to keep.


R5. Menu Commands and Shortcut Keys for Debuggers

The following table lists commands for debuggers from Borland, MS and Symantec. If your debugger is not listed, find out its commands and fill in the table to the right.

Feature Borland Menu Borland Shortcut MSVC Menu MSVC Shortcut Symantec Menu Symantec Shortcut Your debugger
Run Run | Run Ctrl + F9 Build | Debug | Go F5 Debug | Start/Restart debugging F4
Step Over Run | Step Over F8 Debug | Step Over F10 Window | Debug View | Step Over F10
Step Into Run | Trace Into F7 Debug | Step Into F11 Window | Debug View | Step Into F8
Output Screen View | User screen Alt + F5 View | Output Alt + 2 Windows | Debug View | Output Ctrl + Shift + O
Reset Debug | Program Reset Ctrl+ F2 Debug | Stop Debugging Shift + F5 Window | Debug Toolbox | Reset Ctrl+ F2
Inspect Debug | Inspect Alt + F4 View | Variables or Debug | Quickwatch Alt + 3 or Shift + F9 Windows | View Toolbox | Inspector Ctrl + Shift + N
Watch Debug | Watches | Add watch Ctrl + F7 View | Watch or View | Debug Menu | Watch Alt + 4 or Alt + 3 Windows | View Toolbox | Watch Ctrl + Shift + W
View Watch Window | Watch Ctrl + F7 View | Watch Alt + 4 Windows | View Toolbox | Watch Ctrl + Shift + W
Add Breakpoint Debug | Breakpoints n/a Edit | Breakpoints Alt + F9 Windows | Debug View | Add breakpoint Ctrl + Shift + B
Toggle Breakpoint Debug | Toggle breakpoint Ctrl+F8 Edit | Breakpoints Alt + F9 Windows | Debug View | Toggle breakpoint F9


Do not forget to send your answers when you are finished.