算法设计与分析ch0

DesignandAnalysisofComputerAlgorithms

骆吉洲计算机科学与工程系课程介绍Instructor:

骆吉洲Room:A315Office:

科技大厦，6011房间

Telephone:

（0451）86415280-20Email:

InformationaboutInstructorClassNewsWillbepostedbyInternetPleasegivemeyouremailaddressesClassMaterialsYouwillfindtheminaddress:Http:///coursesHomeworkandExam.HomeworkandReading:

20%FinalExam(WrittenTest):

80%

InformationaboutClassWhattoTeachNPPNPOOutlineofthecourseChapter1.Introduction1.1RoleofAlgorithmsinComputerScience1.2

Algorithms1.3

AnalyzingAlgorithms1.4

DesigningAlgorithmsChapter2.

MathematicalFoundations2.1

GrowthofFunctions2.2

RecurrencesChapter3.Divide-and-conquerAlgorithms

Elementsofdivide-and-conquer

2-DimensionalMaximaFindingProblem

FindingtheClosestPairofPoints3.4FindingtheConvexHullChapter4.

DynamicProgramming

Matrix-chainmultiplication

Elementsofdynamicprogramming

Longestcommonsubsequence

OptimalpolygontriangulationChapter5.GreedyAlgorithms

Anactivity-selectionproblem

Elementsofthegreedystrategy

Huffmancodes

Theoreticalfoundationsforgreedymethods

Atask-schedulingproblemChapter6.

AmortizedAnalysis

Theaggregatemethod

Theaccountingmethod

Thepotentialmethod

DynamictablesChapter7.TreeSearchingStrategies7.1TheBreadth-FirstSearch7.2Depth-FirstSearch7.3HillClimbing7.4Best-FirstSearchStrategy7.5TheBranch-and-BoundStrategyChapter8.Prune-and-Search8.1TheGeneralMethods8.2TheSelectionProblem8.3LinearProgrammingwithTwoVariables8.4The1-CenterProblem

Chapter9.On-LineAlgorithms9.1On-LineEuclideanSpanningTreeAlgorithm9.2On-Linek-ServerProblem9.3On-LineObstacleTraversalAlgorithm9.4OtherOn-LineAlgorithmChapter10.TheoryofNP-Completeness10.1NPProblems10.2Cook’sTheorem10.3NP-CompleteProblems10.4NPOProblemsChapter11.ApproximationAlgorithms11.1

Thevertex-coverproblem11.2

Thetraveling-salesmanproblem11.3

Theset-covingproblem11.4

Thesubset-sumproblemChapter12.RandomAlgorithms12.1Elementsofrandomalgorithms12.2Randomizedselectalgorithm12.3RandomizedQUICKSORTalgorithm12.4Otherrandomizedalgorithms

Chapter12.GeneticAlgorithms12.1TheGeneticAlgorithmsinProblemSolving12.2TheGeneticAlgorithmsinScientificModels12.3TheoreticalFoundationsofGeneticAlgorithmsReferences1.

ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest.IntroductiontoAlgorithms,

TheMITPress,第二版,2002.2.王晓东，计算机算法设计与分析，电子工业出版社，2001。GoodBooks1.

D.E.Knuth等,ArtoftheComputerProgramming,Vol.3,Addison-Wesley,1973.2.,J.D.Ullman等.TheDesignandAnalysisofComputerAlgorithms.Addison-Wesley,1974.3.,等.DataStructuresandAlgorithms.Addison-Wesley,1983.4.

4.S.Baase，ComputerAlgorithms:IntroductiontoDesignandAnalysis.Addison-Wesley,secondedition,1988.5.E.HorowitzandSartajSahni.FundamentalsofComputerAlgorithms.ComputerSciencePress,1978.1.

IEEETransactionsonElectronicComputers2.

IEEETransactionsonSoftwareEngineering3.

IEEETransactionsonDataandKnowledgeEngineering4.

ActaInformatica5.

SIAMJournalonComputing6.

JournalofComputerandSystemSciences7.

CommunicationoftheACM8.

JournaloftheACM9.

BITImportantJournals10.

InformationandControl11.

ACMComputingSurveys12.

MathematicsofComputation13.

InformationProcessingLetters14.

TeoreticalComputerScienceImportantConferences1.AnnualACMSymposiumonTheoryofComputing2.AnnualIEEES