Assignment on Data Structures and Algorithms (Doc)

Added on - 09 Oct 2019

3
pages
1133
words
13
views
0
downloads

Share
Share on Facebook Share on Twitter Share on LinkedIn Share on Whatsapp Share on Mail Copy Link
Report
Report
Issue
Duplicate Content
Copyright Issue
Irrelevant Content
Misinformation
Incomplete
Illicit Content
Personal Information
Others
Comment (Optional)
Thank you for your feedback.

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.