国外算法设计与分析课件

ImportantProblemTypesandFundamentalDataStructuresImportantproblemstypesSorting,searching,stringprocessing,graphproblemsFundamentaldatastructuresLineardatastructuresStacks,queues,andheapsGraphsTreesExpectedOutcomesStudentshouldbeabletoListthevariousproblemtypesandtheirmeaningsExplaineachdatastructuresintroducedinthelectureSortingRearrangetheitemsofagivenlistinascending/descendingorder.Input:Asequenceofnnumbers<a1,

a2,…,an>Output:Areordering<a´1,

a´2,…,a´n>oftheinputsequencesuchthata´1≤a´2≤…≤

a´n.Whysorting?HelpsearchingAlgorithmsoftenusesortingasakeysubroutine.SortingkeyAspeciallychosenpieceofinformationusedtoguidesorting.I.e.,sortstudentrecordsbynames.SortingExamplesofsortingalgorithmsBubblesortSelectionsortInsertionsortMergesortQuicksortHeapsort…Evaluatesortingalgorithmcomplexity:thenumberofkeycomparisons.TwopropertiesStability:Asortingalgorithmiscalledstableifitpreservestherelativeorderofanytwoequalelementsinitsinput.Inplace:Asortingalgorithmisinplaceifitdoesnotrequireextramemory,except,possiblyforafewmemoryunits.SearchingFindagivenvalue,calledasearchkey,inagivenset.ExamplesofsearchingalgorithmsSequentialsearchingBinarysearching…StringProcessingAstringisasequenceofcharactersfromanalphabet.Textstrings:letters,numbers,andspecialcharacters.Stringmatching:searchingforagivenword/patterninatext.GraphProblemsLinearDataStructuresArraysAsequenceofnitemsofthesamedatatypethatarestoredcontiguouslyincomputermemoryandmadeaccessiblebyspecifyingavalueofthearray’sindex.LinkedListAsequenceofzeroormorenodeseachcontainingtwokindsofinformation:somedataandoneormorelinkscalledpointerstoothernodesofthelinkedlist.Singlylinkedlist(nextpointer)Doublylinkedlist(next+previouspointers)ArrayofnelementsSinglylinkedlistofnelementsDoublelinkedlistofnelementsStacks,Queues,andHeaps(1)StacksAstackofplatesinsertion/deletioncanbedoneonlyatthetop.LIFO/FILOTwooperations(pushandpop)QueuesAqueueofcustomerswaitingforservicesInsertion/enqueuefromtherearanddeletion/dequeuefromthefront.FIFOTwooperations(enqueueanddequeue)Stacks,Queues,andHeaps(2)

Priorityqueues(implementedusingheaps)

Adatastructureformaintainingasetofelements,eachassociatedwithakey/priority,withthefollowingoperationsFindingtheelementwiththehighestpriorityDeletingtheelementwiththehighestpriorityInsertinganewelementSchedulingjobsonasharedcomputer.GraphsFormaldefinitionAgraphG=<V,E>isdefinedbyapairoftwosets:afinitesetVofitemscalledverticesandasetEofvertexpairscallededges.Undirectedanddirectedgraphs(digraph).What’sthemaximumnumberofedgesinanundirectedgraphwith|V|vertices?Complete,dense,andsparsegraphAgraphwitheverypairofitsverticesconnectedbyanedgeiscalledcomplete.K|V|(a)(b)GraphRepresentationAdjacencymatrixnxnbooleanmatrixif|V|isn.Theelementontheithrowandjthcolumnis1ifthere’sanedgefromithvertextothejthvertex;otherwise0.Theadjacencymatrixofanundirectedgraphissymmetric.AdjacencylinkedlistsAcollectionoflinkedlists,oneforeachvertex,thatcontainalltheverticesadjacenttothelist’svertex.Whichdatastructurewouldyouuseifthegraphisa100-nodestarshape?WeightedGraphsWeightedgraphsGraphsordigraphswithnumbersassignedtotheedges.GraphProperties--PathsandConnectivityPathsApathfromvertexutovofagraphGisdefinedasasequenceofadjacent(connectedbyanedge)verticesthatstartswithuandendswithv.Simplepaths:Alledgesofapatharedistinct.Pathlengths:thenumberofedges,orthenumberofvertices–1.ConnectedgraphsAgraphissaidtobeconnectedifforeverypairofitsverticesuandvthereisapathfromutov.ConnectedcomponentThemaximumconnectedsubgraphofagivengraph.GraphthatisnotconnectedGraphProperties--AcyclicityCycleAsimplepathofapositivelengththatstartsandendsathesamevertex.AcyclicgraphAgraphwithoutcyclesDAG(DirectedAcyclicGraph)TreesTreesAtree(orfreetree)isaconnectedacyclicgraph.Forests:agraphthathasnocyclesbutisnotnecessarilyconnected.Propertiesoftrees|E|=|V|-1Foreverytwoverticesinatreetherealwaysexistsexactlyonesimplepathfromoneoftheseverticestotheother.Why?Rootedtrees:

Theabovepropertymakesitpossibletoselectanarbitraryvertexinafreetreeandconsideritastherootoftheso-calledrootedtree.Levelsofrootedtree.AtreeandaforestRootedTreesancestorsForanyvertexvinatreeT,alltheverticesonthesimplepathfromtheroottothatvertexarecalledancestors.descendantsAlltheverticesforwhichavertexvisanancestoraresaidtobedescendantsofv.parent,childandsiblingsIf(u,v)isthelastedgeofthesimplepathfromtheroottovertexv(andu

v),uissaidtobetheparentofvandviscalledachildofu.Verticesthathavethesameparentarecalledsiblings.LeavesAvertexwithoutchildreniscalledaleaf.SubtreeAvertexvwithallitsdescendantsiscalledthesubtreeofTrootedatv.TransformationofafreetreeintoarootedtreeTreesDepthofavertexThelengthofthesimplepathfromtheroottothevertex.HeightofatreeThelengthofthelongestsimplepathfromtheroottoaleaf.OrderedTreesOrderedtreesAnorderedtreeisarootedtree