I need the program to take in the sample_in file and have an output file as a result. Should be in the instructions. :)
Microsoft Word - ProgrammingAssignment4.docx CISC320Spring2018 ProgrammingAssignment4 Youmayuseanyofthefollowingprogramminglanguages: Java C++/C Python PLTScheme(Racketsubset) Ifyouwouldliketouseadifferentonepleaseletmeknowaheadoftime.Ifyouareusinga specificlibraryotherthanonesIlistpleasealsoletmeknow. Recommendedgraphlibraries: C++:boost,http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/index.html Python:NetworkX,http://networkx.github.io/index.html Java:JGraphT,https://github.com/jgrapht/jgrapht PLTScheme:RacketGenericGraphLibrary,https://docs.racket-lang.org/graph/index.html Testing Youwillbegivenafileasinputwiththename"scenario_in.txt"wherescenariowillbe differentforeachscenarioandwewillexpectwhateverprogramminglanguageyouuseto writeafileasoutputwiththesamenameastheinputfilereplacing"_in.txt"with"_out.txt" (i.e.iftheinputfileis"simple_in.txt"theoutputfileshouldbe"simple_out.txt"). Pleasecheckcanvasforupdatedscenarios.Therewillbesomeadditionalhiddenscenarios thatwewillusetocheckforcorrectnessofimplementation. Grading Gradingwillbethetotalofscoresforthe4parts. Part1=20%ifcorrect Part2=20%ifcorrect Part3=20%ifcorrect Part4=20%ifheuristicispolynomialtimeandsatisfies<= criteria="" part="" 5="20%" if="" correct="" bonus="" credit="up" to="" 25%="" which="" can="" apply="" to="" beyond="" the="" programming="" assignment="" category="" towards="" your="" course="" grade.="" 10%="" of="" this="" will="" be="" based="" on="" internal="" metrics="" and="" 15%="" rewarded="" relative="" to="" peer="" submissions="" (i.e.="" the="" top="" submission="" will="" receive="" 15%;="" all="" other="" solutions="" will="" receive="" an="" amount="" based="" on="" how="" close="" they="" were="" to="" the="" top="" submission).="" problem="" the="" new="" ud="" president,="" dennis="" assanis,="" would="" like="" to="" improve="" the="" student="" experience="" during="" final="" exam="" week="" and="" has="" decided="" to="" host="" a="" study="" break="" party="" on="" reading="" day.="" he="" has="" invited="" all="" of="" the="" faculty,="" staff,="" and="" student="" body="" to="" his="" property="" for="" snacks="" and="" socializing.="" however,="" many="" people="" find="" this="" socially="" awkward="" and="" will="" choose="" to="" stay="" home="" because="" they="" aren't="" really="" friends="" with="" the="" new="" president.="" given="" a="" social="" network="" of="" friends="" we="" can="" predict="" how="" many="" people="" would="" stay="" home="" by="" computing="" the="" average="" social="" awkwardness="" factor.="" in="" figure="" 1="" president="" assanis="" is="" represented="" as="" 1="" and="" 3,="" 4,="" and="" 6="" are="" friends="" with="" the="" president="" and="" are="" considered="" to="" have="" a="" social="" awkwardness="" factor="" of="" 1="" with="" the="" president.="" 10,="" 11,="" 7,="" and="" 2="" have="" a="" social="" awkwardness="" factor="" of="" 2="" with="" the="" president="" and="" 9,="" 8,="" 5="" a="" factor="" of="" 3.="" this="" metric="" assumes="" that="" the="" president="" has="" a="" social="" awkwardness="" factor="" of="" 0="" with="" himself="" and="" has="" no="" qualms="" about="" attending="" his="" own="" study="" break="" party.="" part="" 1:="" given="" a="" scenario="" input="" with="" n="" people="" and="" 1="" party="" host="" compute="" the="" average="" social="" awkwardness="" if="" all="" people="" were="" to="" attend="" the="" party.="" do="" not="" include="" the="" party="" host="" in="" the="" average!="" the="" first="" scenario="" in="" sample_in.txt="" is="" the="" one="" in="" figure="" 1.="" part="" 2:="" president="" assanis="" is="" a="" smart="" fellow="" and="" realizes="" that="" hosting="" multiple="" study="" break="" parties="" would="" lower="" the="" social="" awkwardness="" between="" party="" host="" and="" attendees.="" given="" a="" scenario="" input="" with="" n="" people="" and="" m="" party="" hosts,="" compute="" each="" person's="" social="" awkwardness="" if="" they="" attend="" the="" party="" which="" they="" were="" closest="" to="" the="" host="" (the="" party="" where="" they="" would="" feel="" the="" least="" socially="" awkward).="" report="" the="" average="" social="" awkwardness="" value="" over="" all="" people="" who="" are="" not="" party="" hosts!="" part="" 3:="" the="" president="" realizes="" he="" has="" a="" fixed="" budget="" allowing="" m="" party="" hosts="" and="" that="" he="" might="" not="" be="" able="" to="" choose="" the="" party="" hosts="" that="" minimize="" the="" average="" social="" awkwardness="" without="" the="" help="" of="" our="" cisc320="" class.="" given="" a="" scenario="" input="" with="" n="" people="" and="" a="" number="" m="" (with="" 0="" starting="" assignments="" of="" party="" hosts),="" compare="" the="" following="" 2="" greedy="" heuristics="" by="" computing="" their="" average="" social="" awkwardness="" for="" each="" scenario:="" 1.="" find="" the="" person="" with="" the="" most="" friends="" and="" make="" them="" a="" party="" host.="" repeat="" until="" m="" party="" hosts="" have="" been="" assigned.="" ties="" should="" be="" resolved="" by="" choosing="" the="" person="" with="" a="" lower="" numerical="" id.="" 2.="" first="" pick="" the="" person="" with="" the="" most="" friends="" and="" make="" them="" a="" party="" host.="" on="" subsequent="" rounds,="" find="" the="" person="" with="" the="" maximum="" current="" social="" awkwardness="" and="" make="" them="" a="" party="" host.="" repeat="" until="" m="" party="" hosts="" have="" been="" assigned.="" ties="" should="" be="" resolved="" by="" choosing="" the="" person="" with="" a="" lower="" numerical="" id.="" part="" 4:="" come="" up="" with="" a="" better="" heuristic="" than="" the="" ones="" given="" in="" part="" 3.="" your="" heuristic="" must="" run="" in="" polynomial="" time.="" to="" receive="" credit="" for="" part="" 4="" your="" heuristic="" must="" produce="" at="" least="" one="" scenario="" that="" has="" a="" lower="" average="" social="" awkwardness="" than="" the="" given="" heuristics="" and="" must="" be="" lower="" or="" equal="" to="" the="" given="" heuristics="" for="" all="" scenarios.="" part="" 5:="" create="" a="" new="" version="" of="" your="" heuristic="" that="" is="" called="" when="" the="" budget="" m="" is="" 0.="" in="" this="" scenario="" we="" interpret="" the="" 0="" as="" an="" unknown="" maximum="" of="" party="" hosts="" and="" want="" your="" heuristic="" to="" assign="" as="" many="" parties="" as="" needed="" to="" get="" the="" average="" social="" awkwardness="" to="" 1="" (i.e.="" change="" your="" loop="" from="" "while="" assigned="" hosts="">< max="" hosts:="" assign="" a="" new="" host"="" to="" "while="" average="" awkwardness="">1:assignanewhost").Youroutputshouldhavethesameformataspart4. AdditionalInformationaboutthecontextofthisproblem IfweweretocomeupwithaperfectheuristicforallscenariosforPart4itwouldbeableto solveaknownNP-completeprobleminpolynomialtime.Thedominatingsetproblem couldberepresentedasthedecisionproblem:inaperfectallocationwithNverticesandM partyhostsistheaveragesocialawkwardnessequalto1?Thismightgiveyouahintasto howtocomeupwithareallygoodheuristicforpart4. Inputformat: Thefirstlineoftheinputcontainsthenumberoftestcases.Eachtestcasestartswithone linethathasfouritemsofinformation,separatedbyoneormoreblankspaces: • Thenumberofpeople(N).Itwillbeintherange3..100.IntheFigure1exampleitis11, whichmeansthatthepeopleIDsare1..11. • Thenumberoffriendshiplinks(F)betweenpeople. • Thenumberofparties(M)allowedbythebudget.IntheFigure1exampleitis1. • Thenumberofassignedpartyhosts(A).Itwillbeeither0orM.IntheFigure1example itisMwhichis1. ThenextFlinesofthetestcasecontainapairofnumbers,separatedbyoneormoreblank spaces.Eachpairofnumbersisabi-directionalfriendshiplink.Ifthetwovalueswere1and 2thiswouldmeanthatperson1isafriendwithperson2andthatperson2isafriendwith person1.Therearenoone-directionfriendshiplinks. ThenextAlinesofthetestcasecontainasinglenumberwhichistheIDofapartyhost.In scenarioswhereA=0therewillbenolinesandyourprogramisexpectedtocomputethe partyhostsaccordingtothe2heuristicsinpart3andyourheuristicyoudevelopinpart4. Sampleinputthatwouldtestparts1,2,3,4: 4 111111 14 16 25 62 37 67 31 78 79 103 116 1 111122 14 16 25 62 37 67 31 78 79 103 116 9 1 111155 14 16 25 62 37 67 31 78 79 103 116 1 2 3 6 7 111150 14 16 25 62 37 67 31 78 79 103 116 Sampleoutput.Thisshowspart1working(testcase1),part2working(testcases2,3),and parts3and4working(testcase4).Notethatmysamplepart4heuristicisidenticaltopart3 heuristic2soitwouldearnnopointsforpart4.Pleaseroundto2decimalplacesofprecision. TestCase1. Averagesocialawkwardness=2.00 TestCase2. Averagesocialawkwardness=1.67 TestCase3. Averagesocialawkwardness=1.00 TestCase4. Heuristic1hostsare6,7,1,3,2 Averagesocialawkwardness=1.00 Heuristic2hostsare6,10,4,5,8 Averagesocialawkwardness=1.17 Myheuristichostsare6,10,4,5,8 Averagesocialawkwardness=1.17 5 11 11 1 1 1 4 1 6 2 5 6 2 3 7 6 7 3 1 7 8 7 9 10 3 11 6 1 11 11 2 2 1 4 1 6 2 5 6 2 3 7 6 7 3 1 7 8 7 9 10 3 11 6 9 1 11 11 5 5 1 4 1 6 2 5 6 2 3 7 6 7 3 1 7 8 7 9 10 3 11 6 1 2 3 6 7 11 11 5 0 1 4 1 6 2 5 6 2 3 7 6 7 3 1 7 8 7 9 10 3 11 6 11 11 0 0 1 4 1 6 2 5 6 2 3 7 6 7 3 1 7 8 7 9 10 3 11 6