in this problem, we will use divide-and-conquer to write a program that computes the zeros of a given cubic equation.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Data Structures and Algorithms Programming

Answer the below questions. You may use whatever IDEs / text editors you like, but you must submit your responses on repl.it. Responses will be graded on correctness, code design, and code style.In the below questions, each program will read several lines of input and print one line of output; the contents of these lines are explicitly defined in each problem. The code for reading inputs and writing outputs is provided for you; you need only implement the logic that computes the output. The “run” but- ton on repl.it runs your code using the input from input.txt; to test different test cases, you can modify the contents of input.txt in a way that matches the problem description and example. (If you are using the command line or another IDE to do your work, you can use the command java ClassNameGoesHere< input.txt.)

 

• (40 points) (This is a version of an interview question I once ) In this problem, we will write a program that, given an integer k, an integer n, and a list of integers, outputs the number of pairs in in the list that add to k. To receive full credit for design, your algorithm must have a runtime in O(n), where n is the length of the list of integers. Your program should take as input a number k on its own line, followed by a number n on its own line, followed by a space-separated list of n integers. It should then output the number of pairs in the list that add to k. Order does not mat- ter when considering a pair (in other words, in the list [2,1] there is one distinct pair that sums to 3, not two). You may assume that all numbers in the input are distinct.

 

For example, if our file input.txt is:

1

6

1 2 3 4 -2 -3

then we should print:

2

since there are two pairs that sum to 1: 3+(-2) and 4+(-3). As another example, if input.txt is:

3

4

1 2 3 4

then we should print:

1

since there is one pair that sums to 1: 1+2.

The problem PairFinder provides starter code for reading and printing; your task is to fill in the findPairs() method.

• (60 points) In this problem, we will use divide-and-conquer to write a program 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 ax3 + bx2 + cx + d = 0.

For example, if our file input.txt is:

5

1

7

3

then our goal is to solve the equation 5x3 + x2 + 7x + 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 5x3 + 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 x3 = 0, you must print three lines, each with the string 0.00000. As another example, if your program is given the equation x3 − 4x2 + 4x = 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 problem CubicZeroFinder provides starter code for reading and printing; your task is to fill in the findZeroes() method.

Restrictions:

• 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. You may not upload external libraries and use them in your solution.

• 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, you may wish to have a helper function that represents the quadratic formula (see below). You may also wish to use the nth root finder from Assignment 2 (feel free to copy this code from the solutions if you weren’t able to finish it).

• Any solutions that violate these restrictions will receive a grade of zero for

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

• We can separate cubic equations into the following three types:

  • Some cubic equations have one “saddle point”, where the func- tion is tangent to a horizontal line at one point, but increases everywhere else or decreases everywhere else. Consider the ex- ample of f (x) = x3 and f (x) = −x3.

  • Some cubic equations have no saddle points and have no local max or local min, which will be handled by Step 4.

• All other cubic functions have exactly one local minimum and ex- actly one local maximum. As an example, consider the function f (x) = (x − 1)2(x + 3).

• You can determine all critical points (saddle points, local mins, and local maxes) for a function f (x) = ax3 + bx2 + cx + d by solving the equation (3ax2 + 2bx + c = 0. The quadratic formula, which states√that the zeroes of a function g(x) = ax2 + bx + c are equal to

−b ±

b2 − 4ac

2a

, might be helpful here. This will give either zero,

one or two critical points. If there are zero, go to step 4.

• To determine if a critical point x0 of f (x) = ax3 + bx2 + cx + d is a saddle point, local min, or local max, we can consider the function fjj(x) = 6ax + 2b. If fjj(x0) is negative, x0 is a local maximum. If fjj(x0) is positive, x0 is a local minimum. If fjj(x0) is 0, then x0 is a saddle

Step 2: Find any integer zeroes. Completion of this step should result in your passing test cases #1-4 (8 points).

• If f (x) has a saddle point, then check if it is on the x-axis. If so, then this saddle point is a triple zero of f (x) and we are done. If not, go to Step

• If f (x) has a local min and max, then check if they are both above  the x-axis or both below the x-axis. If so, go to Step

• Check if either the local max or local min is on the x-axis. If so, then that point is a double zero of f (x), 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

• If neither the local max nor the local min is on the x-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

Step 3: Find all real zeroes. Completion of this step should result in your passing test cases #5-8 (8 points).

• Modify your approach from Step 2 to binary search through all real numbers in the specified ranges rather than just the

• You should consider when to stop searching so that your program does not run indefinitely. I would recommend reading through your code for NthRoot

Step 4: In the case when f (x) only crosses the x-axis once in a place that is not a saddle point, f (x) has one real zero and two complex ones. (A

complex zero is one which is written in the form p + qi, where i = √ 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).

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of