Do only Question 2 and have to put it inside of the pdf I AttackedDo in java
CSc 2720: Data Structures and Algorithms Programming Assignment 4 Instructor: Sailesh Kumar Due 9/24/19 11:59 pm 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.)="" (1)="" (40="" points)="" (this="" is="" a="" version="" of="" an="" interview="" question="" i="" once="" saw.)="" 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="" 1="" 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.="" (2)="" (60="" 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="" 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="" 6="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:="" 2="" -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:="" (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.="" you="" may="" not="" upload="" external="" libraries="" and="" use="" them="" in="" your="" solution.="" (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,="" 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).="" (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-="" 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." (ii)="" some="" cubic="" equations="" have="" no="" saddle="" points="" and="" have="" no="" local="" 3="" max="" or="" local="" min,="" which="" will="" be="" handled="" by="" step="" 4.="" (iii)="" 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).="" (b)="" 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.="" (c)="" to="" determine="" if="" a="" critical="" point="" x0="" of="" f(x)="ax" 3="" +="" bx2="" +="" cx="" +="" d="" is="" a="" saddle="" point,="" local="" min,="" or="" local="" max,="" we="" can="" consider="" the="" function="" f="" ′′(x)="6ax" +="" 2b.="" if="" f="" ′′(x0)="" is="" negative,="" x0="" is="" a="" local="" maximum.="" if="" f="" ′′(x0)="" is="" positive,="" x0="" is="" a="" local="" minimum.="" if="" f="" ′′(x0)="" is="" 0,="" then="" x0="" 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(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="" 4.="" (b)="" 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="" 4.="" (c)="" 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="" locations.="" (d)="" 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="" 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="" through="" your="" code="" for="" nthroot="" finder.="" 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="" 4="" 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).="" hints:="" •="" make="" sure="" you="" stay="" organized="" and="" separate="" your="" code="" into="" separate="" meth-="" ods="" and/or="" files="" as="" needed.="" •="" 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="" a="" double="" eval(int="" a,="" int="" b,="" int="" c,="" int="" d,="" double="" x)="" function="" that="" computes="" the="" value="" of="" ax3="" +="" bx2="" +="" cx="" +="" d.="" •="" you="" should="" consider="" writing="" a="" boolean="" isalmostequal(double="" val1,="" double="" val2)="" function="" that="" tells="" you="" whether="" val1="" and="" val2="" are="" within="" some="" small="" value="" of="" each="" other.="" •="" you="" should="" consider="" writing="" a="" double[]="" quadraticformula(double="" a,="" double="" b,="" double="" c)="" function="" that="" solves="" a="" quadratic="" equation="" ax2="" +="" bx="" +="" c="0" •="" you="" should="" consider="" writing="" pow()="" and="" nthroot()="" helper="" functions.="" .="" •="" beware="" of="" infinite="" loops.="" •="" beware="" of="" “negative="" zero”="" (google="" this).="" you="" can="" accommodate="" for="" this="" by="" writing="" something="" like="" x="0.0" +="" x.="" if="" your="" code="" is="" not="" passing="" test="" case="" 1,="" this="" may="" be="" the="" reason="" why!="" •="" nthroot="" solution:="" private="" static="" string="" findnthroot(int="" number,="" int="" n,="" int="" precision)="" {="" initialize="" bounds="" double="" lowerbound="0.0;" double="" upperbound="(double)" number;="" compute="" epsilon,="" which="" represents="" 10^-(2="" *="" precision)="" double="" epsilon="1.0;" for="" (int="" i="0;" i="">< 2*precision; i++) { epsilon *= 0.1; } // iteratively guess the midpoint and check it while (true) { double guess = (lowerbound + upperbound) / 2.0; 5 // compute guess^n double guesstothen = 2*precision;="" i++)="" {="" epsilon="" *="0.1;" }="" iteratively="" guess="" the="" midpoint="" and="" check="" it="" while="" (true)="" {="" double="" guess="(lowerBound" +="" upperbound)="" 2.0;="" 5="" compute="" guess^n="" double="" guesstothen="">