solve the tasks in C++ kindly.

Assignment 04: Recursion

COSC 2336: Data Structures and Algorithms Fall 2020

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 you 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. And by definition there is only 1 way to chose 0 elements (dont choose any). 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

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

Notice that for the binomial coefficient order doesnt 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 n!

i =i!(ni)! (3) Where ! represents the factorial of a number, as we discussed in our textbook.

=3 (1)

=6 (2)

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

i = i1 + i (4)

1

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 together two smaller subproblems. For this recursive definition of the binomial coefficient, the base cases are:

n n

0 = 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 dont 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 unsigned 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 unsigned long int. All of your parameters and return values for the functions in this assignment should be defined to be of type bigint. 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 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.

Setup

For this assignment you will be given the following files:

File Name

assg04-tests.cpp

BinomialFunctions.hpp

BinomialFunctions.cpp

Description

Unit tests for the LargeInteger class you are to write.

Header file declaring for function prototypes of the 4 functions you are to write.

Implementation file of the

4 functions you are to implement for this assignment.

Set up a multi-file project to compile the two .cpp source files together and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. The general approach you should take for this assignment, and all assignment is:

1. Set up your project with the given starting templates. The files should compile and run, but either no tests will be run, or tests will run but be failing.

2. For this project, start by uncommenting the first TEST_CASE in the assg04-tests.cpp file. These are the unit tests to test the functionality of your factorialIterative().

3. AddthecorrectfunctionprototypeforthefactorialIterative()memberfunctiontotheBinomialFunctions.hpp header file. The prototype consists of the name of the function, its input parameters and their types (a biting

in this case), and the return value of the function (also a bigint).

4. Add a stub/empty implementation of factorialIterative() to the BinomialFunctions.cpp implementation file. The function should have the same signature as the prototype you gave in the header file. Documentation for the function has not been given for you this time, so add documentation of your function first. The function should initially just return a 0 result so you can test your project is now compiling and running.

2

5. Your code should compile and run now. Make sure after adding the function prototype and stub your code compiles and runs. However, your unit tests will be failing initially.

6. Incrementally implement the functionality of your factorialIterative() member function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach.

7. Once you have the factorialIterative() function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some member functions use previous ones in this assignment, so do them in the order given for you in the tasks below.

Tasks

You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment:

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

2. Write the factorial function again, but using recursion. Call this function 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 elements 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 function will also count the number of combi- nations of choosing i elements from a set of n items. However, you need to implement this calculation as a recursive function, using the general and base cases described above for counting combinations in equation 4

(general case) and equation 5 (base cases). Your function will take the same two bigint parameters as input n and i with values >= 0, and will return a bigint result.

Example Output

Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output.

$ ./test

===============================================================================

All tests passed (58 assertions in 4 test cases)

$ ./test -s

-------------------------------------------------------------------------------

test is a Catch v2.7.2 host application.

Run with -? for options

-------------------------------------------------------------------------------

iterative factorial implementation

-------------------------------------------------------------------------------

assg04-tests.cpp:30

3

...............................................................................

assg04-tests.cpp:34: PASSED:

CHECK( factorialIterative(0) == 1 )

with expansion:

1 == 1

... output snipped ...

===============================================================================

All tests passed (58 assertions in 4 test cases)

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. There is a target named submit that will create a tared and gziped file named assg04.tar.gz. You should do a make submit when finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment.

$ make submit tar cvfz assg04.tar.gz assg04-tests.cpp assg04-main.cpp BinomialFunctions.hpp BinomialFunctions.cpp assg04-tests.cpp assg04-main.cpp BinomialFunctions.hpp BinomialFunctions.cpp

able to grade your submission.

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

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