Assignment on Data Structures and Algorithms (Doc)

Added on - 09 Oct 2019

  • 3

    pages

  • 1133

    words

  • 13

    views

  • 0

    downloads

Showing pages 1 to 1 of 3 pages
Data Structuresand AlgorithmsObjectivesDesignandimplementaprogrambasedonagreedy algorithmtosolvetheMinimalSpanningTree(MST)problem;Chooseandimplementappropriatedatastructuresforthe algorithm;Analysetheefficiencyofdifferentimplementationsofthealgorithmincomparisonwiththebruteforcealgorithm.TaskYoushouldwriteasingleprogramwhichimplementsPrimsalgorithmwithdifferentdatastructures,aswellasthebruteforcesearchalgorithm,tofindtheMSTofanundirected,connected,weightedgraph.ProgramYourprogramshouldreadasymmetricmatrixfrom atextfilethatdescribesweightededgesofanundirected, connectedgraphandfindtheMSTthatissavedinanoutputfileasasequenceofedgesoftheMST.Theprogramalsodisplaysthe numbersofverticesandedgesinthegraph andthetimespenttofinditsMSTforeachdatastructure usedinPrimsandthebruteforcesearchalgorithms,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.
desklib-logo
You’re reading a preview
card-image

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Unlock This Document