Stefan Hougardy  Jens Vygen Algorithmic Mathematics Algorithmic Mathematics Stefan Hougardy • Jens Vygen Algorithmic Mathematics 123 StefanHougardy JensVygen ResearchInstituteforDiscreteMathematics ResearchInstituteforDiscreteMathematics UniversityofBonn UniversityofBonn Bonn,Germany Bonn,Germany TranslatedbyRabevonRandow,formerlyUniversityofBonn,Germany ISBN978-3-319-39557-9 ISBN978-3-319-39558-6 (eBook) DOI10.1007/978-3-319-39558-6 LibraryofCongressControlNumber:2016955863 ©SpringerInternationalPublishingSwitzerland2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Since the adventof computers,thesignificanceof algorithmshas risensteadily in allfieldsofmathematics.AttheUniversityofBonnthishasledtotheintroduction of a new course of lectures for beginning students, alongside the two basic coursesAnalysisandLinearAlgebra,namelyAlgorithmicMathematics.Thisbook comprisesthecontentofthisnewcoursewhichtheauthorshavetaughtseveraltimes and which consists of around 30 lectures of 90min each, plus exercise tutorials. Whilethebookassumesnomorethanhighschoolknowledge,itischallengingfor readerswithoutmathematicalexperience. In contrast to most other introductory texts on algorithms which are probably intendedpredominantlyfor computerscience students, our emphasisis on a strict and rigorous mathematical presentation. Exact definitions, precise theorems, and carefully executed elegant proofs are in our view indispensable, particularly at thebeginningofmathematicalstudies.Moreover,thebookcontainsmanyworked examples,explanations,andreferencesforfurtherstudy. Our choice of themes reflects our intention to present as wide a spectrum of algorithms and algorithmic problems as possible without a deeper knowledge of mathematics. We treat basic concepts (Chaps.1, 2, and 3), numerical problems (Chaps.4and5),graphs(Chaps.6and7),sortingalgorithms(Chap.8),combinato- rialoptimization(Chaps.9and10),andGaussianelimination(Chap.11).Asthemes areofteninterrelated,theorderofthechapterscannotbechangedwithoutpossibly havingtorefertolatersections.Thereaderwillbeintroducednotonlytotheclassic algorithmsandtheiranalysisbutalsotoimportanttheoreticalfoundationsandwill discovermanycross-referencesandevenunsolvedresearchproblems. Onecannotreallyunderstandalgorithmsandworkwiththemwithoutbeingable to implement them as well. Thus we have, alongside the mathematical themes, includedanintroductionto theprogramminglanguageC++ inthisbook.Indoing so we have, however, endeavored to restrict the technical details to the necessary minimum—this is not a programming course!—while still presenting the student lackingprogrammingexperiencewithanintroductorytext. Our carefully designed programming examples have a twofold purpose: first to illustrate the main elements of C++ and also to motivate the student to delve further,and second to supplementthe relevanttheme. Clearly one cannotbecome a versatile programmerwithout actually doing it oneself, just as one cannot learn v vi Preface mathematics properlywithout doing exercises and solving problemsoneself. One cannotemphasizethistoostronglyandweencourageallbeginningstudentstodoso. It is our sincere wish that all our readers will enjoy studying Algorithmic Mathematics! Bonn,Germany StefanHougardy March2015 JensVygen Remarks on the C++ Programs This book contains a number of programming examples formulated in C++. The source code of all these programs can be downloaded from the websites of the authors. In this book we have used the C++ version specified in ISO/IEC 14882:2011 [5], which is also known as C++11. In order to compile these programmingexamples,one canuse allthe usualC++ compilersthatsupportthis C++ version. For example, the freely available GNU C++ Compiler g++ from version 4.8.1 onwards supports all the language elements of C++11 used in this book.ExamplesofgoodtextbooksonC++11are[25,32].Detailedinformationon C++11isalsoavailableontheinternet,seeforexamplehttp://en.cppreference.com orhttp://www.cplusplus.com. vii Acknowledgments Wewouldliketotaketheopportunitytothankallthosewhohavehelpedusoverthe years with suggestionsand improvementspertaining to this book. Along with the studentstakingourcoursestherearethosethatdeservespecialmention:Christoph Bartoschek,UlrichBrenner,HelmutHarbrecht,StephanHeld,DirkMüller,Philipp Ochsendorf,JanSchneider,andJannikSilvanus.Toallofthemweextendourwarm thanks. We will continue to be very grateful for being made aware of any remaining mistakesoroffurthersuggestionsforimprovement. Bonn,Germany StefanHougardy JensVygen ix Contents 1 Introduction ................................................................ 1 1.1 Algorithms............................................................ 1 1.2 ComputationalProblems............................................. 2 1.3 Algorithms,PseudocodeandC++................................... 4 1.4 ASimplePrimalityTest.............................................. 8 1.5 TheSieveofEratosthenes ........................................... 13 1.6 NotEverythingIsComputable ...................................... 15 2 RepresentationsoftheIntegers .......................................... 21 2.1 Theb-AdicRepresentationoftheNaturalNumbers ............... 21 2.2 Digression:OrganizationoftheMainMemory..................... 25 2.3 Theb’sComplementRepresentationoftheIntegers............... 27 2.4 RationalNumbers.................................................... 30 2.5 ArbitrarilyLargeIntegers............................................ 34 3 ComputingwithIntegers .................................................. 41 3.1 AdditionandSubtraction ............................................ 41 3.2 Multiplication ........................................................ 42 3.3 TheEuclideanAlgorithm............................................ 44 4 ApproximateRepresentationsoftheRealNumbers ................... 49 4.1 Theb-AdicRepresentationoftheRealNumbers................... 49 4.2 MachineNumbers.................................................... 52 4.3 Rounding ............................................................. 53 4.4 MachineArithmetic.................................................. 55 5 ComputingwithErrors ................................................... 57 5.1 BinarySearch......................................................... 58 5.2 ErrorPropagation .................................................... 59 5.3 TheConditionofaNumericalComputationalProblem............ 61 5.4 ErrorAnalysis........................................................ 63 5.5 Newton’sMethod .................................................... 64 6 Graphs ...................................................................... 67 6.1 BasicDefinitions..................................................... 67 6.2 PathsandCircuits .................................................... 69 xi xii Contents 6.3 ConnectivityandTrees............................................... 70 6.4 StrongConnectivityandArborescences ............................ 73 6.5 Digression:ElementaryDataStructures ............................ 74 6.6 RepresentationsofGraphs........................................... 78 7 SimpleGraphAlgorithms ................................................ 85 7.1 GraphTraversalMethods............................................ 85 7.2 Breadth-FirstSearch ................................................. 87 7.3 BipartiteGraphs...................................................... 89 7.4 AcyclicDigraphs..................................................... 90 8 SortingAlgorithms ........................................................ 91 8.1 TheGeneralSortingProblem........................................ 91 8.2 SortingbySuccessiveSelection..................................... 92 8.3 SortingbyKeys ...................................................... 97 8.4 MergeSort............................................................ 98 8.5 QuickSort ............................................................ 100 8.6 BinaryHeapsandHeapSort......................................... 102 8.7 FurtherDataStructures .............................................. 107 9 OptimalTreesandPaths .................................................. 109 9.1 OptimalSpanningTrees ............................................. 109 9.2 ImplementingPrim’sAlgorithm..................................... 112 9.3 ShortestPaths:Dijkstra’sAlgorithm................................ 115 9.4 ConservativeEdgeWeights.......................................... 118 9.5 ShortestPathswithArbitraryEdgeWeights........................ 120 10 MatchingsandNetworkFlows ........................................... 123 10.1 TheMatchingProblem............................................... 123 10.2 BipartiteMatchings .................................................. 124 10.3 Max-Flow-Min-CutTheorem........................................ 126 10.4 AlgorithmsforMaximumFlows .................................... 129 11 GaussianElimination ...................................................... 133 11.1 TheOperationsofGaussianElimination............................ 135 11.2 LUDecomposition................................................... 138 11.3 GaussianEliminationwithRationalNumbers...................... 141 11.4 GaussianEliminationwithMachineNumbers...................... 144 11.5 MatrixNorms......................................................... 147 11.6 TheConditionofSystemsofLinearEquations..................... 150 Bibliography...................................................................... 155 Index............................................................................... 157