Assignment on Data Structures and Algorithms (Doc)

Added on - 09 Oct 2019

3
Pages
1133
Words
107
Views
0
Downloads

Share on Facebook Share on Twitter Share on LinkedIn Share on Whatsapp Share on Mail Copy Link

Trusted by +2 million users,
1000+ happy students everyday

Showing pages 1 to 1 of 3 pages

Data Structuresand AlgorithmsObjectivesDesignandimplementaprogrambasedonagreedy algorithmtosolvetheMinimalSpanningTree(MST)problem;Chooseandimplementappropriatedatastructuresforthe algorithm;Analysetheefficiencyofdifferentimplementationsofthealgorithmincomparisonwiththebruteforcealgorithm.TaskYoushouldwriteasingleprogramwhichimplementsPrim’salgorithmwithdifferentdatastructures,aswellasthebruteforcesearchalgorithm,tofindtheMSTofanundirected,connected,weightedgraph.ProgramYourprogramshouldreadasymmetricmatrixfrom atextfilethatdescribesweightededgesofanundirected, connectedgraphandfindtheMSTthatissavedinanoutputfileasasequenceofedgesoftheMST.Theprogramalsodisplaysthe numbersofverticesandedgesinthegraph andthetimespenttofinditsMSTforeachdatastructure usedinPrim’sandthebruteforcesearchalgorithms,whichcanbesavedin anotheroutputfileaswellforyourlateranalysis.Yourprogramshouldonlymeasurethetimespentbythealgorithmwithitsdata structuretofindtheMSTsothatitisaproperdesigntouseonemethod/functiontoimplementanalgorithm anditsassociateddatastructure.Foranalgorithmthatoperatesonaweightmatrix,ittakestheweightmatrixstoredinatwo-dimensionalarrayasitsparameter;foranalgorithmthatoperates onadjacencylists,ittakesadjacencylistsyoucreatedfromtheweightmatrix.Youmaycreateyourownlistdatastructuresbased on arrays.NoSTLorJavaCollectionorothercollectionframeworkcanbe used.Inthe partofthe algorithmimplementation,youshould notuseanylibraryfunctionsincludingmaximalorminimalfunctions butcreateyourownfunctionsto operate onarrays.Yourprogramshould bereadable andwellcommented.Inaddition,youneedstocreateasmallprogram orscripttogeneratetheweightmatrixforagraphofvariousverticesand edges, savedtoatextfile. Whenyoucreategraphs,youneed considerthedensityandconnectivityofgraphs.Youmayuseaprogram/scriptbyotherpeople,withreferencetothesource,togeneratethesematrices.