Data str and algorithm -Recursion

profileJohn@123
ProgrammingAssignment04RecursionattachedfilesSep172019845PM.zip
Home>Computer Science homework help>Data str and algorithm -Recursion

assg-04.cpp

assg-04.cpp

/** 
 *  @author  Jane Programmer
 *  @cwid    123 45 678
 *  @class   COSC 2336, Spring 2019
 *  @ide     Visual Studio Community 2017
 *  @date    January 12, 2019
 *  @assg    Assignment 04
 * 
 *  @description  Assignment 04 Practice defining recursive functions.  We
 *   implement factorial and counting combinations functions using the
 *   binomial coefficient in this assignment.  This file containts unit
 *   tests of the required functions for this assignment.
 */
#include   < iostream >
#include   < cassert >
#include   < chrono >   // measure elapsed time of functions using high resolution clock
#include   "BinomialFunctions.hpp"

using   namespace  std ;


/** main 
 * The main entry point for this program.  Execution of this program
 * will begin with this main function.
 *
 *  @param  argc The command line argument count which is the number of
 *     command line arguments provided by user when they started
 *     the program.
 *  @param  argv The command line arguments, an array of character
 *     arrays.
 *
 *  @returns  An int value indicating program exit status.  Usually 0
 *     is returned to indicate normal exit and a non-zero value
 *     is returned to indicate an error condition.
 */
int  main ( int  argc ,   char **  argv )
{
   // test iterative version of factorial
  cout  <<   "Testing iterative version factorialIterative() "    <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
  bigint res ;
  
   //res = factorialIterative(0);
   //cout << "Test base case: factorialIterative(0) = " << res << endl;
   //assert(res == 1);

   //res = factorialIterative(1);
   //cout << "Test edge case: factorialIterative(1) = " << res << endl;
   //assert(res == 1);

   //res = factorialIterative(-1);
   //cout << "Test error case: factorialIterative(-1) = " << res << endl;
   //assert(res == 1);

   //res = factorialIterative(10);
   //cout << "Test general case: factorialIterative(10) = " << res << endl;
   //assert(res == 3628800);
  
   //res = factorialIterative(12);
   //cout << "Test general case (largest 32 bit int): factorialIterative(12) = " << res << endl;
   //assert(res == 479001600);

   //res = factorialIterative(20);
   //cout << "Test general case (largest 64 bit int): factorialIterative(20) = " << res << endl;
   //assert(res == 2432902008176640000);

   // timing test for factorialIterative, do it 10000 times and see how much time
   // elapses
   // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
   const   int  NUM_TIMING_LOOPS  =   10000 ;
   //auto start = chrono::high_resolution_clock::now(); 
   //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
   //{
   //  res = factorialIterative(20);
   //}
   //auto finish = chrono::high_resolution_clock::now();
   //chrono::duration<double> elapsed = finish - start;
   //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialIterative(20) "
   //     << elapsed.count() << endl;

  
   // test recursive version of factorial
  cout  <<  endl ;
  cout  <<   "Testing recursive version factorialRecursive() "    <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;

   //res = factorialRecursive(0);
   //cout << "Test base case: factorialRecursive(0) = " << res << endl;
   //assert(res == 1);

   //res = factorialRecursive(1);
   //cout << "Test edge case: factorialRecursive(1) = " << res << endl;
   //assert(res == 1);

   //res = factorialRecursive(-1);
   //cout << "Test error case: factorialRecursive(-1) = " << res << endl;
   //assert(res == 1);

   //res = factorialRecursive(10);
   //cout << "Test general case: factorialRecursive(10) = " << res << endl;
   //assert(res == 3628800);

   //res = factorialRecursive(12);
   //cout << "Test general case (largest 32 bit int): factorialRecursive(12) = " << res << endl;
   //assert(res == 479001600);

   //res = factorialRecursive(20);
   //cout << "Test general case (largest 64 bit int): factorialRecursive(20) = " << res << endl;
   //assert(res == 2432902008176640000);

   //cout << "Test equivalence of iterative and recursive solutions from n=0 to 20: " << endl;
   //for (int n = 0; n <= 20; n++)
   //{
   //  cout << "   Testing n = " << n << "...";
   //  assert(factorialIterative(n) == factorialRecursive(n));
   //  cout << " passed" << endl;
   //}

   // timing test for factorialRecursive, do it 10000 times and see how much time
   // elapses
   // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
   //start = chrono::high_resolution_clock::now(); 
   //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
   //{
   //  res = factorialRecursive(20);
   //}
   //finish = chrono::high_resolution_clock::now();
   //elapsed = finish - start;
   //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialRecursive(20) "
   //     << elapsed.count() << endl;

  
   // test direct calculation version of counting combinations
  cout  <<  endl ;
  cout  <<   "Testing combinations countCombinationsDirectly() "    <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;

   int  i ;
   int  n ;

   //n=5; i=0;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=5; i=5;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=0; i=0;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=5; i=1;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 5);

   //n=4; i=2;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 6);
  
   //n=15; i=6;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 5005);
  
   //n=15; i=14;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 15);

   // max factorial using bigint
   //n=20; i=10;
   //res = countCombinationsDirectly(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 184756);
  
   // timing test for countCobminationsDirectory, do it 10000 times and see how much time
   // elapses
   // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
   //start = chrono::high_resolution_clock::now(); 
   //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
   //{
   //  n=20; i=10;
   //  res = countCombinationsDirectly(n, i);
   //}
   //finish = chrono::high_resolution_clock::now();
   //elapsed = finish - start;
   //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsDirectly("
   //     << "n=" << n << " choose i=" << i << ") :"
   //     << elapsed.count() << endl;
  

   // test recursive calculation version of counting combinations
  cout  <<  endl ;
  cout  <<   "Testing combinations countCombinationsRecursive() "    <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;

   //n=5; i=0;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=5; i=5;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=0; i=0;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 1);
  
   //n=5; i=1;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 5);

   //n=4; i=2;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 6);
  
   //n=15; i=6;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 5005);
  
   //n=15; i=14;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 15);

   // max factorial using bigint
   //n=20; i=10;
   //res = countCombinationsRecursive(n, i);
   //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl;
   //assert(res == 184756);
  
   //cout << "Test equivalence of iterative and recursive solutions for counting combinations" << endl
   //     << "This is an exhaustive test of all combinations of n and i from 0 to 15" << endl;
   //for (n = 0; n <= 15; n++)
   //{
   //  for (i = 0; i <= n; i++)
   //  {
   //    cout << "   Testing (n=" << n << " choose i=" << i << ") equivalence...";
   //    assert(countCombinationsDirectly(n, i) == countCombinationsRecursive(n, i));
   //    cout << " passed" << endl;
   //  }
   //}

   // timing test for countCobminationsRecursive, do it 10000 times and see how much time
   // elapses
   // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c--
   //start = chrono::high_resolution_clock::now(); 
   //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++)
   //{
   //  n=20; i=10;
   //  res = countCombinationsRecursive(n, i);
   //}
   //finish = chrono::high_resolution_clock::now();
   //elapsed = finish - start;
   //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsRecursive("
   //     << "n=" << n << " choose i=" << i << ") :"
   //     << elapsed.count() << endl;

  
   // return 0 to indicate successful completion
   return   0 ;
}

BinomialFunctions.cpp

BinomialFunctions.cpp

/** 
 *  @author  Jane Programmer
 *  @cwid    123 45 678
 *  @class   COSC 2336, Spring 2019
 *  @ide     Visual Studio Community 2017
 *  @date    January 22, 2019
 *  @assg    Assignment 04
 * 
 *  @description  Implementation file of function implementations for
 *   the Binomial Coefficient functions.  We have functions for computing
 *   the factorial of an integer and for counting the number of combinations
 *   of n choose i items in this library.
 */
#include   "BinomialFunctions.hpp"

using   namespace  std ;


BinomialFunctions.hpp

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date January 22, 2019 * @assg Assignment 04 * * @description Header file of definitions for implementation * the Binomial Coefficient functions. We have functions for computing * the factorial of an integer and for counting the number of combinations * of n choose i items in this library. */ #ifndef _BINOMIALFUNCTIONS_H_ #define _BINOMIALFUNCTIONS_H_ #include <iostream> using namespace std; // global definitions typedef long long int bigint; // give long int an alias name of bigint // Function prototypes for our BinomialFunctions library go here #endif // _BINOMIALFUNCTIONS_H_

assg-04.pdf

Assg 04: Recursion

COSC 2336 Data Structures

Objectives

• Practice writing functions

• Practice writing recursive functions.

• Compare iterative vs. recursive implementation of functions.

• Learn to define base case and general case for recursion.

Description

In this assignment we will write a recursive function to calculate what is known as the binomial coefficient. The binomial coefficient is a very useful quantity, it allows us to count the number of combinations of selecting i items out of a set of n elements. For example, if we have 3 items A, B, C, there are 3 ways to choose 1 element from the items: choose A, or choose B or choose C. There are also 3 ways to choose 2 elements from the items: AB, AC, BC. There is only 1 way to choose 3 elements from a set of 3 items: ABC. When we choose 2 elements from a set of 3 items, we normally speak of this as counting the number of combinations of 3 choose 2, and mathematically we write this as a binomial coefficient(

3

2

) = 3 (1)

Where the result of the binomial coefficient is to count up the number of combinations we will have for n items when we select i elements. As another example, just to make this clear, if we have a set of 4 items, ABCD, and we choose 2 elements from this set, we get: AB, AC, AD, BC, BD, CD = 6:(

4

2

) = 6 (2)

1

Notice that for the binomial coefficient order doesn’t matter, thus AB and BA are considered the same when choosing 2 elements from the set of 4, and we end up with only a count of 6 ways to choose 2 items from a set of 4 (look up permutations for a similar concept but where order matters).

Mathematically we can compute directly the number of combinations for n choose i using factorials: (

n

i

) =

n!

i!(n − i)! (3)

Where ! represents the factorial of a number, as we discussed in our textbook.

However, another way of computing the number of combinations is by defining a recursive relationship:(

n

i

) =

( n − 1 i − 1

) +

( n − 1 i

) (4)

You can think of this as the general case of a recursive function that takes two parameters n and i, and computes the answer recursively by adding to- gether two smaller subproblems. For this recursive definition of the binomial coefficient, the base cases are:(

n

0

) =

( n

n

) = 1 (5)

We have already seen why n items choose n elements will always be 1. The other base case is used by definition, and simply means that there is only 1 way of choosing no items from a set (e.g. you don’t choose).

In this assignment we will write several functions. First of all you will write your own version of the factorial function. Actually I want you to write two versions, a recursive version of factorial, and a version that uses a loop (iterative version). We will be using long int (64-bit) instead of regular int (32-bit) for all of the parameters and return values. You will find a typedef given to you in the starting .hpp template:

typedef long int bigint;

A typedef like this is really just an alias or name for the other already known type. In this case bigint means a long int. All of your parameters and return values for the functions in this assignment should be defined to be of type bitint. Why did we use the bigint? Well, the largest result from factorial that will fit into a regular 32-bit int is 12! = 479001600. By

2

using a 64-bit int, we can expand the maximum factorial we can calculate a bit, where 20! = 2432902008176640000 and this fits into a 64-bit integer.

Then you will write two versions of the binomial coefficient to count combinations. One version will use one of your factorial functions to directly count the combinations, using the first formula given above. Then your second version will be a recursive version, that uses the recursive general and base case given to implement counting the number of combinations.

For this assignment you need to perform the following tasks.

1. Write a function called factorialIterative(). This function should take a single BIG integer (bigint) as its parameter n, and it will com- pute the factorial n! of the value and return it as its result (as a bigint). Write this functions using a loop (do not use recursion).

2. Write the factorial function again, but using recursion. Call this func- tion factorialRecursive(). The function takes the same parameters and returns the same result as described in 1.

3. Write a function called countCombinationsDirectly(). This function will compute the number of combinations that result from choosing i el- ements from set of n items. The function should take two bigint values as its parameters n and i, which will be integers >= 0. The function should use the equation 3 above to directly compute the number of combinations. You should use your factorialRecursive() function to compute the factorials in this function.

4. Write a function called countCombinationsRecursive(). This func- tion will also count the number of combinations of choosing i elements from a set of n items. However, you need to implement this calcula- tion as a recursive function, using the general and base cases described above for counting combinations in equation 4 (general case) and equa- tion 5 (base cases). Your function will take the same two bigint pa- rameters as input n and i with values >= 0, and will return a bigint result.

You will again be given 3 starting template files like before, an assg-04.cpp file of tests of your code, and a BinomialFunctions.hpp and BinomialFunc- tions.cpp header and implementation file. As before, you should practice incremental development, and uncomment the tests in the assg-04.cpp file one at a time, and implement the functions in the order shown. If you im- plement your code correctly and uncomment all of the tests, you should get the following correct output:

3

Testing iterative version factorialIterative() ------------------------------------------------------------- Test base case: factorialIterative(0) = 1 Test edge case: factorialIterative(1) = 1 Test error case: factorialIterative(-1) = 1 Test general case: factorialIterative(10) = 3628800 Test general case (largest 32 bit int): factorialIterative(12) = 479001600 Test general case (largest 64 bit int): factorialIterative(20) = 2432902008176640000 Elapsed time 10000 loops of factorialIterative(20) 0.000880682

Testing recursive version factorialRecursive() ------------------------------------------------------------- Test base case: factorialRecursive(0) = 1 Test edge case: factorialRecursive(1) = 1 Test error case: factorialRecursive(-1) = 1 Test general case: factorialRecursive(10) = 3628800 Test general case (largest 32 bit int): factorialRecursive(12) = 479001600 Test general case (largest 64 bit int): factorialRecursive(20) = 2432902008176640000 Test equivalence of iterative and recursive solutions from n=0 to 20:

Testing n = 0... passed Testing n = 1... passed Testing n = 2... passed Testing n = 3... passed Testing n = 4... passed Testing n = 5... passed Testing n = 6... passed Testing n = 7... passed Testing n = 8... passed Testing n = 9... passed Testing n = 10... passed Testing n = 11... passed Testing n = 12... passed Testing n = 13... passed Testing n = 14... passed Testing n = 15... passed Testing n = 16... passed Testing n = 17... passed Testing n = 18... passed Testing n = 19... passed Testing n = 20... passed

4

Elapsed time 10000 loops of factorialRecursive(20) 0.00179999

Testing combinations countCombinationsDirectly() ------------------------------------------------------------- Test base case: n=5 choose i=0: 1 Test base case: n=5 choose i=5: 1 Test edge case: n=0 choose i=0: 1 Test general case: n=5 choose i=1: 5 Test general case: n=4 choose i=2: 6 Test general case: n=15 choose i=6: 5005 Test general case: n=15 choose i=14: 15 Test general case: n=20 choose i=10: 184756 Elapsed time 10000 loops of countCombinationsDirectly(n=20 choose i=10) :0.00309266

Testing combinations countCombinationsRecursive() ------------------------------------------------------------- Test base case: n=5 choose i=0: 1 Test base case: n=5 choose i=5: 1 Test edge case: n=0 choose i=0: 1 Test general case: n=5 choose i=1: 5 Test general case: n=4 choose i=2: 6 Test general case: n=15 choose i=6: 5005 Test general case: n=15 choose i=14: 15 Test general case: n=20 choose i=10: 184756 Test equivalence of iterative and recursive solutions for counting combinations This is an exhaustive test of all combinations of n and i from 0 to 15

Testing (n=0 choose i=0) equivalence... passed Testing (n=1 choose i=0) equivalence... passed Testing (n=1 choose i=1) equivalence... passed Testing (n=2 choose i=0) equivalence... passed Testing (n=2 choose i=1) equivalence... passed Testing (n=2 choose i=2) equivalence... passed Testing (n=3 choose i=0) equivalence... passed Testing (n=3 choose i=1) equivalence... passed Testing (n=3 choose i=2) equivalence... passed Testing (n=3 choose i=3) equivalence... passed Testing (n=4 choose i=0) equivalence... passed Testing (n=4 choose i=1) equivalence... passed Testing (n=4 choose i=2) equivalence... passed Testing (n=4 choose i=3) equivalence... passed

5

Testing (n=4 choose i=4) equivalence... passed Testing (n=5 choose i=0) equivalence... passed Testing (n=5 choose i=1) equivalence... passed Testing (n=5 choose i=2) equivalence... passed Testing (n=5 choose i=3) equivalence... passed Testing (n=5 choose i=4) equivalence... passed Testing (n=5 choose i=5) equivalence... passed Testing (n=6 choose i=0) equivalence... passed Testing (n=6 choose i=1) equivalence... passed Testing (n=6 choose i=2) equivalence... passed Testing (n=6 choose i=3) equivalence... passed Testing (n=6 choose i=4) equivalence... passed Testing (n=6 choose i=5) equivalence... passed Testing (n=6 choose i=6) equivalence... passed Testing (n=7 choose i=0) equivalence... passed Testing (n=7 choose i=1) equivalence... passed Testing (n=7 choose i=2) equivalence... passed Testing (n=7 choose i=3) equivalence... passed Testing (n=7 choose i=4) equivalence... passed Testing (n=7 choose i=5) equivalence... passed Testing (n=7 choose i=6) equivalence... passed Testing (n=7 choose i=7) equivalence... passed Testing (n=8 choose i=0) equivalence... passed Testing (n=8 choose i=1) equivalence... passed Testing (n=8 choose i=2) equivalence... passed Testing (n=8 choose i=3) equivalence... passed Testing (n=8 choose i=4) equivalence... passed Testing (n=8 choose i=5) equivalence... passed Testing (n=8 choose i=6) equivalence... passed Testing (n=8 choose i=7) equivalence... passed Testing (n=8 choose i=8) equivalence... passed Testing (n=9 choose i=0) equivalence... passed Testing (n=9 choose i=1) equivalence... passed Testing (n=9 choose i=2) equivalence... passed Testing (n=9 choose i=3) equivalence... passed Testing (n=9 choose i=4) equivalence... passed Testing (n=9 choose i=5) equivalence... passed Testing (n=9 choose i=6) equivalence... passed Testing (n=9 choose i=7) equivalence... passed Testing (n=9 choose i=8) equivalence... passed

6

Testing (n=9 choose i=9) equivalence... passed Testing (n=10 choose i=0) equivalence... passed Testing (n=10 choose i=1) equivalence... passed Testing (n=10 choose i=2) equivalence... passed Testing (n=10 choose i=3) equivalence... passed Testing (n=10 choose i=4) equivalence... passed Testing (n=10 choose i=5) equivalence... passed Testing (n=10 choose i=6) equivalence... passed Testing (n=10 choose i=7) equivalence... passed Testing (n=10 choose i=8) equivalence... passed Testing (n=10 choose i=9) equivalence... passed Testing (n=10 choose i=10) equivalence... passed Testing (n=11 choose i=0) equivalence... passed Testing (n=11 choose i=1) equivalence... passed Testing (n=11 choose i=2) equivalence... passed Testing (n=11 choose i=3) equivalence... passed Testing (n=11 choose i=4) equivalence... passed Testing (n=11 choose i=5) equivalence... passed Testing (n=11 choose i=6) equivalence... passed Testing (n=11 choose i=7) equivalence... passed Testing (n=11 choose i=8) equivalence... passed Testing (n=11 choose i=9) equivalence... passed Testing (n=11 choose i=10) equivalence... passed Testing (n=11 choose i=11) equivalence... passed Testing (n=12 choose i=0) equivalence... passed Testing (n=12 choose i=1) equivalence... passed Testing (n=12 choose i=2) equivalence... passed Testing (n=12 choose i=3) equivalence... passed Testing (n=12 choose i=4) equivalence... passed Testing (n=12 choose i=5) equivalence... passed Testing (n=12 choose i=6) equivalence... passed Testing (n=12 choose i=7) equivalence... passed Testing (n=12 choose i=8) equivalence... passed Testing (n=12 choose i=9) equivalence... passed Testing (n=12 choose i=10) equivalence... passed Testing (n=12 choose i=11) equivalence... passed Testing (n=12 choose i=12) equivalence... passed Testing (n=13 choose i=0) equivalence... passed Testing (n=13 choose i=1) equivalence... passed Testing (n=13 choose i=2) equivalence... passed

7

Testing (n=13 choose i=3) equivalence... passed Testing (n=13 choose i=4) equivalence... passed Testing (n=13 choose i=5) equivalence... passed Testing (n=13 choose i=6) equivalence... passed Testing (n=13 choose i=7) equivalence... passed Testing (n=13 choose i=8) equivalence... passed Testing (n=13 choose i=9) equivalence... passed Testing (n=13 choose i=10) equivalence... passed Testing (n=13 choose i=11) equivalence... passed Testing (n=13 choose i=12) equivalence... passed Testing (n=13 choose i=13) equivalence... passed Testing (n=14 choose i=0) equivalence... passed Testing (n=14 choose i=1) equivalence... passed Testing (n=14 choose i=2) equivalence... passed Testing (n=14 choose i=3) equivalence... passed Testing (n=14 choose i=4) equivalence... passed Testing (n=14 choose i=5) equivalence... passed Testing (n=14 choose i=6) equivalence... passed Testing (n=14 choose i=7) equivalence... passed Testing (n=14 choose i=8) equivalence... passed Testing (n=14 choose i=9) equivalence... passed Testing (n=14 choose i=10) equivalence... passed Testing (n=14 choose i=11) equivalence... passed Testing (n=14 choose i=12) equivalence... passed Testing (n=14 choose i=13) equivalence... passed Testing (n=14 choose i=14) equivalence... passed Testing (n=15 choose i=0) equivalence... passed Testing (n=15 choose i=1) equivalence... passed Testing (n=15 choose i=2) equivalence... passed Testing (n=15 choose i=3) equivalence... passed Testing (n=15 choose i=4) equivalence... passed Testing (n=15 choose i=5) equivalence... passed Testing (n=15 choose i=6) equivalence... passed Testing (n=15 choose i=7) equivalence... passed Testing (n=15 choose i=8) equivalence... passed Testing (n=15 choose i=9) equivalence... passed Testing (n=15 choose i=10) equivalence... passed Testing (n=15 choose i=11) equivalence... passed Testing (n=15 choose i=12) equivalence... passed Testing (n=15 choose i=13) equivalence... passed

8

Testing (n=15 choose i=14) equivalence... passed Testing (n=15 choose i=15) equivalence... passed

Elapsed time 10000 loops of countCombinationsRecursive(n=20 choose i=10) :11.1177

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp source files to the submission folder to complete this assignment. You really do not need to give me the assg-04.cpp file again, as I will have my own file with additional tests of your functions. However, please leave the names of the other two files as BinomialFunctions.hpp and BinomialFunctions.cpp when you submit them.

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.

2. 20 pts for implementing the factorialIterative() function correctly.

3. 25 pts for implementing the factorialRecursive() function correctly.

4. 15 pts for implementing the countCombinationsDirectly() function correctly.

5. 30 pts for implementing the countCombinationsRecursive() function correctly.

6. 5 pts. All output is correct and matches the correct example output.

7. 5 pts. Followed class style guidelines, especially those mentioned below.

Program Style

Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation

9

levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.

2. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.

10