文档介绍：LectureSchedule
TeuBJectoplcsFeadinghw
1PrefminarfesAnayZI99nE
2Asymptcticnotation1018lout
3*RecurrenceRelations
4Modeling1825
5DataStructsElementarydatastructures2730
6,Binarysearchtrees3031
7Redblacktrees175179
8SortingHeapsort3137lin
9*Quicksort37502out
10【Linearsorting236239
Catalogproblems
MIDTERM1
11DecompositionElementsofdynamicprog5365
12Examplesofdynamicprog6575
13Divideandconquer75772in
14【GraphAlgsDatastructuresforgraphs81883out
15Breadthdepthfirstsearch8892
16【Topsortconnectivity9297
17Minimumspanningtrees97100
18Singlesourceshortestpaths100102
19Alpairsshortestpaths2792833in
MIDTERM2
20SearchCombinatorialsearch1151254out
21Heurtsticmethods125136
Catalogproplems
22IntractabilityReductions139144
23*Satisfiabiltty14414745
24Harderreductions147146
2581CooksTheorem
261Approximationalgorithms156160
CatalogProplemsSin
Graduateonlylecturesdenotedwith
VhatISsAnAlgorithm2
Algorithmsaretheideasbehindcomputerprograms.
Analgorithmisthethingwhichstaysthesamewhether
theprogramisinPascalrunningonaCrayinNewYork
orisinBASICrunningonaMacintoshinKathmandul
Tobeinteresting,analgorithmhastosolveagenerall
specifiedproblem,Analgorithmicproblemisspecified
bydescribingthesetofinstancesitmustworkonand
whatdesiredpropertiestheoutputmusthave,
ExampleSorting
InputASequenceofNnumbersal...an
Outputthepermutationreorderingoftheinputse
quenceSUChaSal人aa一an,
Weseekalgorithmswhicharecoryectandefficient,
Correctness
Foranyalgorithm,wemustprovethatia1waySreturns
thedesiredoutputforalllegalinstancesoftheproblemm.
Forsorting,thismeansevenif1theinputisalready
sorted,or2itcontainsrepeatedelements.
CorrectnessisNotbviousi
Thefollowingproblemarisesofteninmanufacturing
andtransportationtestingapplications,
Supposeyouhavearobotarmequippedwithatool
Sayasolderingiron,Toenabletherobotarmtodo
asolderingjob,wemustconstructanorderingofthe
contactpoints,sotherobotvisitsandsoldersthe
firstcontactpoint,thenvisitsthesecondpoint,third
andsoforthuntilthejobisdone,
Sincerobotsareexpensive,Weneedtofindtheorder
w