Description
1 Recursion (10 points)
Create a file called Factorial.java. This file should have the following method:
public static int calculate(int n) Factorial.calculate should recursively calculate n!, where 0! = 1 and n! = n(n−1)!. The method should also print out an error and exit if n < 0 or n 12, since factorial is not defined for negative numbers and will overflow Java’s int variable with larger numbers. Inside Factorial.java, also include a main method which runs a couple of tests on Factorial.calculate:
java Factorial Factorial.calculate(0) returned 1. Test passed! Factorial.calculate(5) returned 120. Test passed! (Obviously, if these tests do not return 1 and 120 respectively, the tests should fail and print out an appropriate message.)
2 Fibonacci revisited (10 points)
Create a file called FibTest.java. Refactor your Fib.java from assignment 1 to be a static method in FibTest. Odds are that your assignment 1 answer is coded in iterative style, where you are looping from 1 to n and adding up numbers as you go. If not, you should write an iterative Fibonacci calculator that does so (and refactor the version that you wrote for assignment 1 for the next part of the problem). This method should be called
public static int fibIter(int n) The recurrence relation for the Fibonacci sequence is the following: fib(1) = 1 fib(2) = 1 fib(n) = fib(n−1) + fib(n−2) Write another static method in the same FibTest class, this time in recursive style, using this relationship.
public static int fibRecur(int n) In FibTest’s main method, write a series of tests that establishes that both of these functions work correctly. Finally, using Java’s System.currentTimeMillis() function, print out the time it takes to execute FibTest.fibIter(40) and FibTest.fibRecur(40).
1
3 π revisited (10 points)
In Assignment 1, you used the Gregory formula to compute an approximation of π. Here, you will use Ramanujan’s series, discovered in 1910. It converges much faster than Gregory’s, and has been used to calculate pi to billions of digits. Implement Ramanujan.java exactly like Gregory.java, taking a number k specified by the user on the command line and calculating π using the first k terms of the Ramanujan series. The program should print this approximate value of π, as well as the percentage difference between this value and the one provided by Java in the constant Math.PI. Ramanujan’s series: 1 π = 2√2 9801 ∞ Pk =0 (4k)!(1103+26390k) (k!)43964k Notice that this formula makes use of the factorial function. Call your Factorial.calculate method from Problem 1. Extra credit: Look at the Java API definitions of BigDecimal and BigInteger. Rework your Factorial and Ramanujan code to use these instead, and calculate π to 100 digits or more. You will get a little extra credit simply by explaining (in comments in your Ramanujan code) how BigDecimal and BigInteger differ from ordinary doubles and ints, and why the latter are insufficient for calculating very precise values of π.
4 Root finding (20 points)
The roots of a continuous function are points at which the value of the function is equal to zero. If we happen to know a value for which the function is positive and another value for which it is negative, then we know for certain that somewhere between the two values lies a zero. In other words, if f(a) 0 and f(b) < 0, then there exists a value x between a and b for which f(x) = 0. This fact suggests that we can zero in on the value of x using the following algorithm, where is the amount of error we are willing to tolerate:
1. Compute x, where x is halfway between a and b, ie x = (a+b) 2 . 2. If |a−x| < return x. 3. If f(x) has the same sign as f(a), the root lies between x and b. Recursively perform the algorithm with x as the new a.
4. Otherwise, the root lies between a and x. Recursively perform the algorithm with x as the new b.
Write a class FunctionTest.java and implement the following method:
public static double findRoot(double a, double b, double epsilon)
Within findRoot(), use Math.sin() as the function to be evaluated. In your main function, print out the root of sin(x) that falls between 3 and 4, to within 0.00000001. Does the number look familiar?
2
5 Polynomials (30 points) Write a class Poly.java to represent polynomials (ie, functions of the form axn +bxn−1 +···+cx2 + dx + e). Implement the following methods:
• Poly(int[] coefficients): Constructor for an array of coefficients where c[n] is the coefficient of xn. In other words, the polynomial 2x5 + 3x4 −8x2 + 4 would be represented by the array [4,0,−8,0,3,2]. • int degree(): Return the power of the highest non-zero term • String toString(): Overriding the Object class’s toString method, this should return a String representation of the polynomial using x as the variable, arranged in decreasing order of exponent and printing nothing for terms with a coefficient of zero. For example, the Poly represented by the array [4,0,−8,0,3,2] should return the string:
"2x^5+3x^4-8x^2+4"
• Poly add(Poly a): To add two polynomials, simply add together each scale degree in turn. Thus, (2x5 + 3x4 −8x2 + 4) + (x3 + 4x2 −2x) = (2x5 + 3x4 + x3 −4x2 −2x + 4). Create a method that constructs and returns a new Poly object with a new coefficient array created by adding the coefficients of the current object and the Poly object a passed as an argument to the add() function. • double evaluate(double x): Return the value of the function at the point x. In other words, if the Poly object represents 2x5 +3x4−8x2 +4 and evaluate(2.0) is called, the method should calculate 2(2)5 + 3(2)4 −8(2)2 + 4 and return 84. Within the main() method of the Poly class, create a series of tests which exercise each of these methods and report their success or failure.
6 Inheritance (20 points)
The findRoot() function in FunctionTest.java works great, but only specifically for the sine function. That’s nice and all, but hardly general. We would like to be able to use the same code for any function at all, and we will use inheritance to make that happen. Create a new class called Function.java that supports an abstract method:
public abstract double evaluate(double x)
Refactor your FunctionTest.findRoot() method so that it belongs to the Function class, and instead of calling Math.sin(), it calls this evaluate() method. Write a class SinFunc.java that extends Function and implements evaluate() using Math.sin(). Write a similar class CosFunc.java that does the same for Math.cos(). Copy your code from Poly.java into a new class PolyFunc.java which also extends Function. Look at that – you’ve already implemented evaluate() for Poly.
3
In Function.main(), create some tests. Instantiate a few SinFunc and CosFunc objects and find some roots. Verify that the root of sin(x) between 3 and 4 is the same as it was before. Find the root of cos(x) between 1 and 3. Find the positive root (x 0) of x2 −3 and x2 −x−2. Finally, for all of the classes in this problem (Function.java, SinFunc.java, CosFunc.java and PolyFunc.java), write javadoc comments explaining the purpose of each class and the uses of each method.
Turning in
You should have created nine Java files for this assignment: Factorial.java, FibTest.java, Ramanujan.java, FunctionTest.java, Poly.java, Function.java, SinFunc.java, CosFunc.java and PolyFunc.java. Ensure that all of them can be compiled and run from the command line. Create a zip file called assignment 2