Starter Code:

import java.util.Scanner;

public class CubicZeroFinder { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // Read in a, b, c, and d for our // equation ax^3 + bx^2 + cx + d = 0 int a = Integer.parseInt(sc.nextLine()); int b = Integer.parseInt(sc.nextLine()); int c = Integer.parseInt(sc.nextLine()); int d = Integer.parseInt(sc.nextLine()); // Find the zeroes String[] zeroes = findZeroes(a, b, c, d); // Print the zeroes, one per line for (int i = 0; i

Code in Java, please add comments for my understanding, will rate thumbs up if right

(30 points) In this problem, we will use divide-and-conquer to write a pro- gram that computes the zeros of a given cubic equation. While a cubic formula exists, it is a proven fact that there is no formula that can solve every polynomial of degree 5, for example, and so it is important to con- sider numerical solutions like the one we will explore here that generalize to higher-degree polynomials. You may assume that the zeroes of these equations lie between -100 and 100 and that distinct ze- roes differ by at least 0.01. Your program should take as input four numbers, each on their own line, representing a, b, c, d (in that order) in the equation az" + bx2 + cx + d = 0 For example, if our file input.txt is 5 7 3 then our goal is to solve the equation 53 + 22 +7a 3 0. You may assume that a 0 The output of your program should be the three solutions of your equa- tion, each on their own line. Each solution must be rounded to five decimal places and ordered in increasing order by real part and then by imaginary part. For example, if we are solving the equation 5z3 +x2 +7x +3 0 as above, your output should be: -0.40464 0.10232-1.21340i 0.10232+1.21340i If your solution has a multiple root, you must print your answer that many times. For example, if your program is given the equation z3- 0, you must print three lines, each with the string 0.00000. As another example if your program is given the equation 3 - 42 4 0, which can also be written as x(x - 2)2-0, your output should be the following 0.00000 2.00000 2.00000 The class CubicZeroFinder provides starter code for reading and print- ing; your task is to fill in the findZeroes) method. Restrictions: (a) You may not use any functions in the Math library, and you may not write any additional import statements beyond those in the starter code or upload external libraries to Vocareum. (b) You may not use the cubic formula (i.e. the cubic analog of the quadratic formula), nor may you use any approach that is mathemat- ically equivalent to hardcoding the cubic formula. (Most solutions that you might find on the Internet fall into this category.) However, adratic formula (see below). You may also wish to use the nth root finder from Problem Set 2 (feel free to copy this code from the solutions if you may wish to have a helper function that represents the qu you weren't able to finish it) (c) Any solutions that violate these restrictions will receive a grade of zero for correctness. You may take any approach you wish, as long as it does not violate the above restrictions. I recommend the following divide-and-conquer ap- proach: Step 1: Find the saddle point or the local min and max of f(x) (a) We can separate cubic equations into the following three types: (i) Some cubic equations have one "saddle point", where the func- t, but increases everywhere else or decreases everywhere else. Consider the ex tion is tangent to a horizontal line at one poin ample of f(x)3 and f(x)-3 max or local min, which will be handled by Step 4 (ii) Some cubic equations have no saddle points and have no local (iii) All other cubic functions have exactly one local minimum and ex actly one local maximum. As an example, consider the function (b) You can determine all critical points (saddle points, local mins, and local maxes) for a function f(z)aba2cr d by solving the equation 3az22bz c 0. The quadratic formula, which states that the zeroes of a function g(r)-ar2 + bx +c are equal to , might be helpful here. This will give either zero one or two critical points. If there are zero, go to step 4 (c) To determine if a critical point o of f(x)bz2 c d is a saddle point, local min, or local max, we can consider the function f"(z) = 6az + 2b. If f"(zo) is negative, zo is a local maximum. If f" (ro) is positive, o is a local minimum. If f"(o) is 0, then o is a saddle point Step 2: Find any integer zeroes. Completion of this step should result in your passing test cases #1-4 (8 points) (a) If f(z) has a saddle point, then check if it is on the r-axis. If so, then this saddle point is a triple zero of f(x) and we are done. If not, go to Step 4. (b) If f(x) has a local min and max, then check if they are both above the r-axis or both below the y-axis. If so, go to Step 4 (c) Check if either the local max or local min is on the r-axis. If so, then that point is a double zero of f(z), which gives us two of our answers. To find the third, we can use binary search to check the integers between -100 and the leftmost critical point, as well as the integers between the rightmost critical point and 100; it will be in one of those two locations (d) If neither the local max nor the local min is on the z-axis, then we can conclude that one zero is between the local max and the local min, one is between -100 and the leftmost critical point, and one is between the rightmost critical point and 100. Binary searching for all of these will give us our three zeroes Step 3: Find all real zeroes. Completion of this step should result in your passing test cases #5-8 (8 points) (a) Modify your approach from Step 2 to binary search through all real numbers in the specified ranges rather than just the integers. (b) You should consider when to stop searching so that your program does not run indefinitely. I would recommend reading the solutions to Problem Set 2 #8 Step 4: In the case when f(x) only crosses the r-axis once in a place that is not a saddle point, f() has one real zero and two complex ones. (A complex zero is one which is written in the form p+ qi, where i-v-1) I leave the approach here to you, but you may find it useful to read about a technique called "synthetic division" on Wikipedia. Completion of this step should result in your passing test cases #9-10 (2 points) Hints: Make sure you stay organized and separate your code into separate meth- ods and/or files as needed. If you had trouble with Problem Set 2 #8, I recommend thoroughly re- viewing the solutions I posted. I highly recommend following the above step-by-step process. I would also recommend having some branches of your code be hardcoded to return dummy values while you work on getting the other cases correctly (in particular, the "Go to Step 4" cases) . You should consider writing an eval(int a, int b, int c, int d, double x) function that computes the value of arbr2 crd. . You should consider writing an isAlmostEqual (double vall, double val2) function that tells you whether vall and val2 are within some small value of each other . You should consider writing a quadraticFormula(double a, double b, double c) function that solves a quadratic equation ar2 + bx + c= 0 . You should consider writing pow() and squareRoot) helper functions. Feel free to copy/paste my solution for the nth root problem from Problem Set 2 #8 . As in Problem Set 2, beware of infinite loops. Beware of Java's "negative zero" (Google this). You can accommodate for this by writing something like x0.0 + x. If your code is not passing Test Case 1, this may be the reason why! (30 points) In this problem, we will use divide-and-conquer to write a pro- gram that computes the zeros of a given cubic equation. While a cubic formula exists, it is a proven fact that there is no formula that can solve every polynomial of degree 5, for example, and so it is important to con- sider numerical solutions like the one we will explore here that generalize to higher-degree polynomials. You may assume that the zeroes of these equations lie between -100 and 100 and that distinct ze- roes differ by at least 0.01. Your program should take as input four numbers, each on their own line, representing a, b, c, d (in that order) in the equation az" + bx2 + cx + d = 0 For example, if our file input.txt is 5 7 3 then our goal is to solve the equation 53 + 22 +7a 3 0. You may assume that a 0 The output of your program should be the three solutions of your equa- tion, each on their own line. Each solution must be rounded to five decimal places and ordered in increasing order by real part and then by imaginary part. For example, if we are solving the equation 5z3 +x2 +7x +3 0 as above, your output should be: -0.40464 0.10232-1.21340i 0.10232+1.21340i If your solution has a multiple root, you must print your answer that many times. For example, if your program is given the equation z3- 0, you must print three lines, each with the string 0.00000. As another example if your program is given the equation 3 - 42 4 0, which can also be written as x(x - 2)2-0, your output should be the following 0.00000 2.00000 2.00000 The class CubicZeroFinder provides starter code for reading and print- ing; your task is to fill in the findZeroes) method. Restrictions: (a) You may not use any functions in the Math library, and you may not write any additional import statements beyond those in the starter code or upload external libraries to Vocareum. (b) You may not use the cubic formula (i.e. the cubic analog of the quadratic formula), nor may you use any approach that is mathemat- ically equivalent to hardcoding the cubic formula. (Most solutions that you might find on the Internet fall into this category.) However, adratic formula (see below). You may also wish to use the nth root finder from Problem Set 2 (feel free to copy this code from the solutions if you may wish to have a helper function that represents the qu you weren't able to finish it) (c) Any solutions that violate these restrictions will receive a grade of zero for correctness. You may take any approach you wish, as long as it does not violate the above restrictions. I recommend the following divide-and-conquer ap- proach: Step 1: Find the saddle point or the local min and max of f(x) (a) We can separate cubic equations into the following three types: (i) Some cubic equations have one "saddle point", where the func- t, but increases everywhere else or decreases everywhere else. Consider the ex tion is tangent to a horizontal line at one poin ample of f(x)3 and f(x)-3 max or local min, which will be handled by Step 4 (ii) Some cubic equations have no saddle points and have no local (iii) All other cubic functions have exactly one local minimum and ex actly one local maximum. As an example, consider the function (b) You can determine all critical points (saddle points, local mins, and local maxes) for a function f(z)aba2cr d by solving the equation 3az22bz c 0. The quadratic formula, which states that the zeroes of a function g(r)-ar2 + bx +c are equal to , might be helpful here. This will give either zero one or two critical points. If there are zero, go to step 4 (c) To determine if a critical point o of f(x)bz2 c d is a saddle point, local min, or local max, we can consider the function f"(z) = 6az + 2b. If f"(zo) is negative, zo is a local maximum. If f" (ro) is positive, o is a local minimum. If f"(o) is 0, then o is a saddle point Step 2: Find any integer zeroes. Completion of this step should result in your passing test cases #1-4 (8 points) (a) If f(z) has a saddle point, then check if it is on the r-axis. If so, then this saddle point is a triple zero of f(x) and we are done. If not, go to Step 4. (b) If f(x) has a local min and max, then check if they are both above the r-axis or both below the y-axis. If so, go to Step 4 (c) Check if either the local max or local min is on the r-axis. If so, then that point is a double zero of f(z), which gives us two of our answers. To find the third, we can use binary search to check the integers between -100 and the leftmost critical point, as well as the integers between the rightmost critical point and 100; it will be in one of those two locations (d) If neither the local max nor the local min is on the z-axis, then we can conclude that one zero is between the local max and the local min, one is between -100 and the leftmost critical point, and one is between the rightmost critical point and 100. Binary searching for all of these will give us our three zeroes Step 3: Find all real zeroes. Completion of this step should result in your passing test cases #5-8 (8 points) (a) Modify your approach from Step 2 to binary search through all real numbers in the specified ranges rather than just the integers. (b) You should consider when to stop searching so that your program does not run indefinitely. I would recommend reading the solutions to Problem Set 2 #8 Step 4: In the case when f(x) only crosses the r-axis once in a place that is not a saddle point, f() has one real zero and two complex ones. (A complex zero is one which is written in the form p+ qi, where i-v-1) I leave the approach here to you, but you may find it useful to read about a technique called "synthetic division" on Wikipedia. Completion of this step should result in your passing test cases #9-10 (2 points) Hints: Make sure you stay organized and separate your code into separate meth- ods and/or files as needed. If you had trouble with Problem Set 2 #8, I recommend thoroughly re- viewing the solutions I posted. I highly recommend following the above step-by-step process. I would also recommend having some branches of your code be hardcoded to return dummy values while you work on getting the other cases correctly (in particular, the "Go to Step 4" cases) . You should consider writing an eval(int a, int b, int c, int d, double x) function that computes the value of arbr2 crd. . You should consider writing an isAlmostEqual (double vall, double val2) function that tells you whether vall and val2 are within some small value of each other . You should consider writing a quadraticFormula(double a, double b, double c) function that solves a quadratic equation ar2 + bx + c= 0 . You should consider writing pow() and squareRoot) helper functions. Feel free to copy/paste my solution for the nth root problem from Problem Set 2 #8 . As in Problem Set 2, beware of infinite loops. Beware of Java's "negative zero" (Google this). You can accommodate for this by writing something like x0.0 + x. If your code is not passing Test Case 1, this may be the reason why