Clifford Stein – författare

Der "Cormen" bietet eine umfassende und vielseitige Einführung in das moderne Studium von Algorithmen. Es stellt viele Algorithmen Schritt für Schritt vor, behandelt sie detailliert und macht deren Entwurf und deren Analyse allen Leserschichten zugänglich. Sorgfältige Erklärungen zur notwendigen Mathematik helfen, die Analyse der Algorithmen zu verstehen. Den Autoren ist es dabei geglückt, Erklärungen elementar zu halten, ohne auf Tiefe oder mathematische Exaktheit zu verzichten. Jedes der weitgehend eigenständig gestalteten Kapitel stellt einen Algorithmus, eine Entwurfstechnik, ein Anwendungsgebiet oder ein verwandtes Thema vor. Algorithmen werden beschrieben und in Pseudocode entworfen, der für jeden lesbar sein sollte, der schon selbst ein wenig programmiert hat. Zahlreiche Abbildungen verdeutlichen, wie die Algorithmen arbeiten. Ebenfalls angesprochen werden Belange der Implementierung und andere technische Fragen, wobei, da Effizienz als Entwurfskriterium betont wird, die Ausführungen eine sorgfältige Analyse der Laufzeiten der Programme mit ein schließen. Über 1000 Übungen und Problemstellungen und ein umfangreiches Quellen- und Literaturverzeichnis komplettieren das Lehrbuch, dass durch das ganze Studium, aber auch noch danach als mathematisches Nachschlagewerk oder als technisches Handbuch nützlich ist. Für die dritte Auflage wurde das gesamte Buch aktualisiert. Die Änderungen sind vielfältig und umfassen insbesondere neue Kapitel, überarbeiteten Pseudocode, didaktische Verbesserungen und einen lebhafteren Schreibstil. So wurden etwa - neue Kapitel zu van-Emde-Boas-Bäume und mehrfädigen (engl.: multithreaded) Algorithmen aufgenommen, - das Kapitel zu Rekursionsgleichungen überarbeitet, sodass es nunmehr die Teile-und-Beherrsche-Methode besser abdeckt, - die Betrachtungen zu dynamischer Programmierung und Greedy-Algorithmen überarbeitet; Memoisation und der Begriff des Teilproblem-Graphen als eine Möglichkeit, die Laufzeit eines auf dynamischer Programmierung beruhender Algorithmus zu verstehen, werden eingeführt. - 100 neue Übungsaufgaben und 28 neue Problemstellungen ergänzt. Umfangreiches Dozentenmaterial (auf englisch) ist über die Website des US-Verlags verfügbar.

TheannualworkshoponAlgorithmEngineeringandExperiments(ALENEX) providesaforumforthepresentationoforiginalresearchintheimplementation andexperimentalevaluationofalgorithmsanddatastructures. ALENEX2002 wasthefourthworkshopinthisseries. ItwasheldinSanFrancisco,California onJanuary4-5,2002. Thisvolumecollectsextendedversionsofthe15papers thatwereselectedforpresentationfromapoolof34submissions. Wewouldliketothankthesponsors,authors,andreviewerswhohelpedmake ALENEX2002asuccess. Wealsowanttothanktheinvitedspeakers,Cynthia PhillipsofSandiaNationalLaboratories,MartinFarach-ColtonofGoogle,and MichaelKassofPixar. Finally,wewouldliketothankSpringer-Verlagfor- blishingthesepapersintheirLectureNotesinComputerScience series. May2002 DavidM. Mount Cli?ordStein ALENEX2002Sponsors Thefollowingorganizationsprovideddirect?nancialsupport,whichenabledus tohostinvitedspeakersandprovidereducedregistrationfeesforstudents. *SandiaNationalLaboratories *AkamiTechnologiesInc. *NECResearch Thefollowingprovidedin-kindsupport,facilitatingtheworkshop.*SIAM,theSocietyforIndustrialandAppliedMathematics *SIGACT,theACMSIGonAlgorithmsandComputationTheory *ColumbiaUniversity ALENEX2002ProgramCommittee NancyAmato(TexasA&MUniversity) MarshallBern(XeroxPARC) MichaelGoodrich(UniversityofCalifornia,Irvine) TomMcCormick(UniversityofBritishColumbia) MichaelMitzenmacher(HarvardUniversity) DavidMount(UniversityofMaryland;Co-chair) GiriNarasimhan(FloridaInternationalUniversity) RajeevRaman(UniversityofLeicester) Cli?ordStein(ColumbiaUniversity;Co-chair) VI ALENEX2002 ALENEX2002SteeringCommittee MichaelGoodrich(UniversityofCalifornia,Irvine) AdamBuchsbaum(AT&TLabs) RobertoBattiti(UniversityofTrento,Italy) AndrewV. Goldberg(IntertrustSTARLab) MichaelT. Goodrich(UniversityofCalifornia,Irvine) DavidS. Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E. Moret(UniversityofNewMexico;chair) JackSnoeyink(UNC-ChapelHill) TableofContents ALENEX2002 OntheImplementationofMST-BasedHeuristicsfortheSteinerProblem inGraphs...1 M. PoggideArag"ao,R. F. Werneck(CatholicUniversityof RiodeJaneiro) ATime-SensitiveSystemforBlack-BoxCombinatorialOptimization ...16 V. Phan,P. Sumazin,S.Skiena(SUNYStonyBrook) ACompressedBreadth-FirstSearchforSatis?ability ...29 D. B. Motter,I. L. Markov(UniversityofMichigan) UsingMulti-levelGraphsforTimetableInformationinRailwaySystems . . 43 F. Schulz,D. Wagner(UniversityofKonstanz),C. Zaroliagis (UniversityofPatras) EvaluatingtheLocalRatioAlgorithmforDynamicStorageAllocation ...60 K. Pruhs(UniversityofPittsburgh),E. Wiewiora(Universityof California,SanDiego) An Experimental Study of Prefetching and Caching Algorithms for the WorldWideWeb ...71 M. Curcio,S. Leonardi,A. Vitaletti (Universit'adiRoma"LaSapienza") TheTreewidthofJavaPrograms...86 J. Gustedt(LORIA&INRIALorraine),O. A. Maehle,J. A. Telle (UniversityofBergen) PartitioningPlanarGraphswithCostsandWeights...98 L. Aleksandrov(BulgarianAcademyofSciences,CarletonUniversity), H. Djidjev(UniversityofWarwick),H. Guo,A. Maheshwari (CarletonUniversity) MaintainingDynamicMinimumSpanningTrees:AnExperimentalStudy . 111 G. Cattaneo,P. Faruolo,U. F. Petrillo(Universit'adiSalerno), G. F. Italiano(Universit'adiRoma"TorVergata") ExperimentalEvaluationofaNewShortestPathAlgorithm ...126 S. Pettie,V. Ramachandran,S. Sridhar(UniversityofTexasatAustin) GettingMorefromOut-of-CoreColumnsort...143 G. Chaudhry,T. H. Cormen(DartmouthCollege) VIII TableofContents TopologicalSweepinDegenerateCases ...155 E. Rafalin,D. Souvaine(TuftsUniversity),I. Streinu(SmithCollege) AccelerationofK-MeansandRelatedClusteringAlgorithms...166 S. J. Phillips(AT&TLabs-Research) STAR-Tree:AnE?cientSelf-AdjustingIndexforMovingObjects ...178 C. M. Procopiuc(AT&TResearchLab),P. K. Agarwal (DukeUniversity),S. Har-Peled(UniversityofIllinois) AnImprovementonTreeSelectionSort...194 J. Chen(BellLabsResearch,Beijing) AuthorIndex...207 OntheImplementationofMST-Based HeuristicsfortheSteinerProbleminGraphs Marcus Poggi de Arag" ao and Renato F. Werneck DepartmentofInformatics,CatholicUniversityofRiodeJaneiro,R. MarquesdeS"ao Vicente,225,RiodeJaneiro,RJ,22453-900,Brazil. poggi@inf. puc-rio. br,rwerneck@cs. princeton. edu Abstract. Someofthemostwidelyusedconstructiveheuristicsforthe Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine e?cient implem- tations of heuristics based on the classic algorithms by Prim, Kruskal, and Bor? uvka.