Factorials

Handle large values

1. Complete the implementation of the Factorials.bigRecursive method, following the same recursive approach used in Factorials.longRecursive, but computing the factorial value using instances of the BigInteger class.

2. Create and implement two new parameterized test methods in FactorialsTest to test Factorials.bigRecursive:

   1. The first of the new methods must take test cases from both the factorials-long.csv file and the factorials-big.csv file, asserting that the values returned from Factorials.bigRecursive are equal to those in the CSV files for the given values of n.

   2. The second method must take test cases from factorials-negative.csv file, asserting that every invocation of Factorials.bigRecursive with an n value in that file results in the corresponding exception being thrown.

Compute long factorials via iteration

1. Complete the implementation of the Factorials.longIterative method, using the iterative computation method given in (1) to compute the factorial of the n parameter value. Don’t forget to handle negative values of n by throwing an IllegalArgumentException.

2. Define two more parameterized test methods in FactorialsTest to test Factorials.longIterative. These methods must test the non-exceptional and exceptional conditions (respectively), taking test cases from factorials-long.csv for the non-exceptional condition tests, and from factorials-negative.csv and factorials-long-overflow.csv for the exceptional condition tests.

Compute BigInteger factorials via iteration

1. Complete the implementation of the Factorials.bigIterative method, using the iterative computation method given in (1) to compute the factorial of the n parameter value. Don’t forget to handle negative values of n by throwing an IllegalArgumentException.

2. Define two more parameterized test methods in FactorialsTest to test Factorials.longIterative. These methods must test the non-exceptional and exceptional conditions (respectively), taking test cases from factorials-long.csv and factorials-big.csv for the non-exceptional test cases, and from factorials-negative.csv for the exceptional cases.

Eliminate unnecessary checks in recursive implementations

If you examine your Factorials.longRecursive and Factorials.bigRecursive methods, you’ll probably notice that the check for invalid n values (and the consequent throwing of an IllegalArgumentException) will take place not only on the invocation for some n, but also on the recursive invocations for (n - 1), (n - 2), etc. However, this check is needed only on the first invocation for n, not for the recursive invocations used in the computation of n!.

Try to modify Factorials.longRecursive and Factorials.bigRecursive to eliminate these unnecessary additional checks. This can be done a few different ways; try to find a way that not only eliminates the unnecessary checks, but also reduces (or eliminates) duplicated code between Factorials.longRecursive and Factorials.bigRecursive. (Hint: Consider helper methods—and note that these can be recursive, just like the ones you’ve written so far in this exercise.)

Don’t forget to run your tests after this change, to make sure that your implementations still behave as expected!

Palindromes

Handle denormalized input values

Currently, the Palindromes.recursive method can only handle input parameter values that are precise palindromes; that is, all letter casing, whitespace, and punctuation in the parameter value provided by a given invocation must also match when reversed. In most cases, this will not give the desired results unless any argument passed to that method is already normalized—with whitespace and punctuation removed, and all characters converted to one letter case. In this task, you’ll address this shortcoming, and add test cases that include whitespace, punctuation, and mixed case.

1. Modify Palindromes.recursive, so that a normalized String is constructed from the input parameter value—i.e. with all non-alphanumeric characters removed, and converted to a single letter case—before testing that normalized String to see if it is a palindrome. (Hint: The regular expression [\W_]+ matches a sequence of one or more non-alphanumeric characters; consider using this with the replaceAll method of the String class, to perform the first part of the normalization.)

2. Define a new parameterized method in the PalindromesTest class, to test your changes on palindromes with whitespace, punctuation, and mixed case. This method must take test cases from the palindromes-denormalized.csv file, and assert that the value returned from your modified Palindromes.recursive is true for all the test cases.

3. Define another parameterized method in PalindromesTest, to test your changes on non-palindromes with whitespace, punctuation, and mixed case. This method must take test cases from the non-palindromes-denormalized.csv file, and assert that the value returned from your modified Palindromes.recursive is false for all the test cases.

Test for palindromes via iteration

1. Complete the implementation of the Palindromes.iterative method, using an iterative approach to the traditional definition in (3)—for example, iterating over the characters of a String, comparing corresponding characters from the left and right sides of the String to each other.

   Important: Please note that your code is expected to perform the actual iteration. In other words, if you find some method in the standard library (or a 3^rd-party library) that returns in input String in reversed form, and then you test the 2 strings (original and reversed) using String.equals), that is not sufficient for this task.

   Don’t forget to include the same input normalization that you added to your recursive implementation in the previous task!

2. Add four more parameterized test methods to the PalindromesTest class, to test your Palindromes.iterative implementation. Remember to name these methods according to the method being tested (aka the method under test), as well as the kind of test case handled by the test method.

   The type of test case and the CSV file containing the test cases for each of the test methods is shown in the following table. (Note that these are the same CSV files you’ve used for the previous test methods in PalindromesTest; all are located in the edu/cnm/deepdive subdirectory of the src/test/resources root.)

   Type of test case	Test cases source file
   Normalized palindromes	palindromes-normalized.csv
   Normalized non-palindromes	non-palindromes-normalized.csv
   Denormalized palindromes	palindromes-denormalized.csv
   Denormalized non-palindromes	non-palindromes-denormalized.csv

Eliminate unnecessary renormalization

If you examine your Palindromes.recursive method, you may notice that—similar to the redundant check for negative values in the recursive factorials methods—the normalization of the input parameter value is happening on each invocation, including all of the recursive invocations required to test any non-trivial string. However, after this normalization is performed on the first invocation, it’s not needed on the subsequent recursive invocation(s).

Try to modify Palindromes.recursive to eliminate the redundant normalizations. This can be done a few different ways; try to find a way that not only eliminates them in Palindromes.recursive, but also reduces (or eliminates) duplicated code between Palindromes.recursive and Palindromes.iterative. (Hint: Consider helper methods again.)

Don’t forget to run your tests after this change, to make sure that your implementations still behave as expected!