Consider the Fibonacci number defined as f(n) = f(n-2) + f(n-1),
where f(0)=0, and f(1)=1.
Extend the interface org.pg4200.ex04.Fibonacci by providing a recursive implementation.
Develop a test class called FibonacciImplTest that
does extend org.pg4200.ex04.FibonacciTestTemplate,
in which you test your FibonacciImpl implementation.
If it is correct, all but 1 test should pass.
Even if the implementation is correct, 1 test will run "forever" without a stack overflow,
due to the exponential complexity of a naive recursive version of Fibonacci.
A naive recursive version of Fibonacci is extremely inefficient, as it does an exponential number
of function calls.
When for example we compute f(100), we need to compute f(98) and f(99).
Once we are done with f(98), and we start to compute f(99), then f(99) = f(97) + f(98),
in which we have to recompute f(98).
Unfortunately, this problem happens an exponential number of times.
To solve this issue, we are going to use a technique called memoization.
Create a new version called FibonacciImplMemoized, in which internally it keeps track of an
array x of values (e.g., x.length=100).
Each time we compute f(n) for the first time, we will store its result in x, i.e., x[n]=f(n).
Each time we ask for f(n), we check first if the value was already computed and stored in x.
In such case, we make no recursive call, and rather directly return x[n].
Develop a test class called FibonacciImplMemoizedTest that
does extend org.pg4200.ex04.FibonacciTestTemplate,
in which you test your FibonacciImplMemoized implementation.
If it is correct, all tests should pass.
Write a class MixedSort that extends MySort. It should implement a Merge Sort algorithm.
However, when recursively it arrives to sort a sub-section of the array with size less than
a certain threshold, eg high - low < bubbleLimit where bubbleLimit can be for example 4,
then it should rather use a Bubble Sort to sort that subsection of the array.
Explain what might be the possible benefits of doing something like this.
Write a test class that extends SortTestTemplate to test if your MixedSort implementation is correct.
Study the source code of MergeSort and QuickSort.
Once you think you fully understand them, write their implementation
on paper (e.g., using a pen), without looking at the source code.
Once done, compare what you wrote with the actual implementations.
Consider the following starting point for a Triangle Classification class:
public class TriangleClassification {
public enum Classification {NOT_A_TRIANGLE, ISOSCELES, SCALENE, EQUILATERAL}
public static Classification classify(int a, int b, int c) {
return null;
}
}
Without looking at the code of TriangleClassification from Exercise 01,
implement such function using TDD.
In particular, when doing TDD, use/write the following tests (each one should
be in its own @Test function), in sequence, one at a time:
- a negative
a<0should result inNOT_A_TRIANGLE - a negative
b<0should result inNOT_A_TRIANGLE - a negative
c<0should result inNOT_A_TRIANGLE - a zero
a==0should result inNOT_A_TRIANGLE - a zero
b==0should result inNOT_A_TRIANGLE - a zero
c==0should result inNOT_A_TRIANGLE - (-1,-1,-1), ie all -1s, should result in
NOT_A_TRIANGLE - (0,0,0), ie all 0s, should result in
NOT_A_TRIANGLE - (1,1,1), ie all 1s, should result in
EQUILATERAL - all edges being
Integer.MAX_VALUE, ie (MAX,MAX,MAX), should result inEQUILATERAL - (1,2,2) should result in
ISOSCELES - (2,1,2) should result in
ISOSCELES - (2,2,1) should result in
ISOSCELES - (5,2,2), ie too large
a, should result inNOT_A_TRIANGLE - (2,5,2), ie too large
b, should result inNOT_A_TRIANGLE - (2,2,5), ie too large
c, should result inNOT_A_TRIANGLE - (MAX-1,MAX,MAX) should result in
ISOSCELES - (MAX,MAX-1,MAX) should result in
ISOSCELES - (MAX,MAX,MAX-1) should result in
ISOSCELES - (2,3,4) should result in
SCALENE - (MAX,MAX-1,MAX-2) should result in
SCALENE
Solutions to this exercise can be found in the solutions
module, under the org.pg4200.sol04 package.