算法设计与分析ch0

《算法设计与分析ch0》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DesignandAnalysisofComputerAlgorithms骆吉洲计算机科学与工程系课程介绍©DB-LAB(2003)Instructor:骆吉洲Room:A315Office:科技大厦，6011房间Telephone:（0451）86415280-20Email:luojizhou@hit.edu.cnInformationaboutInstructor©DB-LAB(2003)ClassNewsWillbepostedbyInternetPleasegivemeyouremailaddressesClassMaterialsYouwillfind

2、theminaddress:Http://db.hit.edu.cn/coursesHomeworkandExam.HomeworkandReading:20%FinalExam(WrittenTest):80%InformationaboutClass©DB-LAB(2003)WhattoTeachNPPNPO©DB-LAB(2003)OutlineofthecourseChapter1.Introduction1.1RoleofAlgorithmsinComputerScience1.2  Algorithms1.3 AnalyzingAlgorithms1.

3、4  DesigningAlgorithmsChapter2.  MathematicalFoundations2.1  GrowthofFunctions2.2  Recurrences©DB-LAB(2003)Chapter3.Divide-and-conquerAlgorithms3.1Elementsofdivide-and-conquer3.22-DimensionalMaximaFindingProblem3.3FindingtheClosestPairofPoints3.4FindingtheConvexHullChapter4.DynamicPro

4、gramming4.1Matrix-chainmultiplication4.2Elementsofdynamicprogramming4.3Longestcommonsubsequence4.4Optimalpolygontriangulation©DB-LAB(2003)Chapter5.GreedyAlgorithms5.1Anactivity-selectionproblem5.2Elementsofthegreedystrategy5.3Huffmancodes5.4Theoreticalfoundationsforgreedymethods5.5Ata

5、sk-schedulingproblemChapter6.AmortizedAnalysis6.1Theaggregatemethod6.2Theaccountingmethod6.3Thepotentialmethod6.4Dynamictables©DB-LAB(2003)Chapter7.TreeSearchingStrategies7.1TheBreadth-FirstSearch7.2Depth-FirstSearch7.3HillClimbing7.4Best-FirstSearchStrategy7.5TheBranch-and-BoundStrat

6、egyChapter8.Prune-and-Search8.1TheGeneralMethods8.2TheSelectionProblem8.3LinearProgrammingwithTwoVariables8.4The1-CenterProblem©DB-LAB(2003)Chapter9.On-LineAlgorithms9.1On-LineEuclideanSpanningTreeAlgorithm9.2On-Linek-ServerProblem9.3On-LineObstacleTraversalAlgorithm9.4OtherOn-LineAlg

7、orithmChapter10.TheoryofNP-Completeness10.1NPProblems10.2Cook’sTheorem10.3NP-CompleteProblems10.4NPOProblems©DB-LAB(2003)Chapter11.ApproximationAlgorithms11.1  Thevertex-coverproblem11.2  Thetraveling-salesmanproblem11.3  Theset-covingproblem11.4  Thesubset-sumproblemChapter12.RandomA

8、lgori