Principles of Algorithmic Problem Solving

1 Principles of Algorithmic Problem SolvingJohan SannemoOctober 24, 2018iiThis version of the book is a preliminary draft. Expect tofind typos and other mistakes. If you do, please reportthem Before report-ing a bug, please check whether it still exists in the lat-est version of this draft, available ~jsannemo/ this BookxiI Preliminaries11 Algorithms and Problems .. Languages .. Code .. Kattis Online Judge .. Exercises .. Notes .. 142 Programming in C++ Environments .. the C++ tools .. World! .. and Types .. and Output .. Statements .. Loops .. Loops .. Structures .. Arrays .. The Preprocessor .. Template .. Additional Exercises .. Chapter Notes .. 503 The C++ Standard .. End of File.

2 Line by Line .. Decimal Precision .. Additional Exercises .. Chapter Notes .. 684 Implementation Exercises .. Notes .. 865 Time Complexity of Insertion Sort .. Notation .. Complexity .. problems .. Types of Complexities .. Importance of Constant Factors .. Exercises .. Notes .. 1016 Foundational Data Arrays .. Matrices .. Lists .. Maps .. Queues .. Trees .. Notes .. 120II Basics1217 Brute Problems .. and Test .. Parameters .. in the Middle .. Notes .. 1408 Greedy Substructure .. Optimal Choices .. Notes .. 1489 Dynamic Path in a DAG .. Programming .. Computation .. of Computation and Memory Usage .. DP .. DP .. DP.

3 Problems .. Common Subsequence .. Cover .. Notes .. 16810 Divide and Inductive Constructions .. Merge Sort .. Binary Search .. Optimization Problems .. Searching in a Sorted Array .. Generalized Binary Search .. Karatsuba s algorithm .. Chapter Notes .. 19011 Data Disjoint Sets .. Range Queries .. Prefix Precomputation .. Sparse Tables .. Segment Trees .. Chapter Notes .. 20112 Graph Breadth-First Search .. Depth-First Search .. Weighted Shortest Path .. Dijkstra s Algorithm .. Bellman-Ford .. Floyd-Warshall .. Minimum Spanning Tree .. Chapter Notes .. 219 CONTENTSvii13 Maximum Flow Networks .. Edmonds-Karp .. Augmenting Paths .. Finding Augmenting Paths.

4 Applications of Flows .. Chapter Notes .. 23014 Tries .. String Matching .. Hashing .. The Parameters of Polynomial Hashes .. 2D Polynomial Hashing .. Chapter Notes .. 25215 The Addition and Multiplication Principles .. Permutations .. Permutations as Bijections .. Ordered Subsets .. Binomial Coefficients .. Dyck Paths .. Catalan Numbers .. The Principle of Inclusion and Exclusion .. Invariants .. Monovariants .. Chapter Notes .. 28416 Number Divisibility .. Prime Numbers .. The Euclidean Algorithm .. Modular Arithmetic .. Chinese Remainder Theorem .. Euler s totient function .. Chapter Notes .. 31217 Competitive Programming IOI .. Strategy .. Getting Better.

5 ICPC .. Strategy .. Getting Better .. 320A Discrete Logic .. Sets and Sequences .. Sums and Products .. Graphs .. Chapter Notes .. 332 Bibliography335 Index337 PrefaceAlgorithmic Problem Solving is the art of formulating efficient methods thatsolve problems of a mathematical nature. From the many numerical algo-rithms developed by the ancient Babylonians to the founding of graph theoryby Euler, Algorithmic Problem Solving has been a popular intellectual pursuitduring the last few thousand years. For a long time, it was a purely mathemati-cal endeavor with algorithms meant to be executed by hand. During the recentdecades Algorithmic Problem Solving has evolved. What was mainly a topic ofresearch became a mind sport known as competitive programming. As a sportalgorithmic Problem Solving rose in popularity with the largest competitionsattracting tens of thousands of programmers.

6 While its mathematical coun-terpart has a rich literature, there are only a few books on algorithms with astrong Problem Solving purpose of this book is to contribute to the literature of Algorithmic prob -lem Solving in two ways. First of all, it tries to fill in some holes in existingbooks. Many topics in Algorithmic Problem Solving lack any treatment at allin the literature at least in English books. Much of the content is insteaddocumented only in blog posts and solutions to problems from various com-petitions. While this book attempts to rectify this, it is not to detract from thosesources. Many of the best treatments of an Algorithmic topic I have seen areas part of a well-written solution to a Problem . However, there is value incompleteness and coherence when treating such a large area. Secondly, I hopeto provide another way of learning the basics of Algorithmic Problem solvingby helping the reader build an intuition for Problem Solving .

7 A large part ofthis book describes techniques using worked-through examples of examples attempt not only to describe the manner in which a problemis solved, but to give an insight into how a thought process might be guidedixxCONTENTSto yield the insights necessary to arrive at a book is different from pure programming books and most other algo-rithm textbooks. Programming books are mostly either in-depth studies of aspecific programming language or describe various programming single language is used in this book C++. The text on C++ exists for thesole purpose of enabling those readers without prior programming experi-ence to implement the solutions to algorithm problems. Such a treatment isnecessarily minimal and teach neither good coding style nor advanced pro-gramming concepts. Algorithm textbooks teach primarily algorithm analysis,basic algorithm design, and some standard algorithms and data seldom include as much Problem Solving as this book does.

8 The bookalso falls somewhere between the practical nature of a programming bookand the heavy theory of algorithm textbooks. This is in part due to the book sdual nature of being not only about Algorithmic Problem Solving , but alsocompetitive programming to some extent. As such there is more real codeand efficient C++ implementations of algorithms included compared to mostalgorithm and foremost, thanks to Per Austrin who providedmuch valuable advice and feedback during the writing of this book. Thanks toSimon and M rten who have competed with me for several years as OmogenHeap. Finally, thanks to several others who have read through drafts andcaught numerous mistakes of my this BookThis book consists of two parts. The first part contains some preliminarybackground, such as algorithm analysis and programming in C++.

9 Withan undergraduate education in computer science most of these chapters areprobably familiar to you. It is recommended that you at least skim throughthe first part since the remainder of the book assumes you know the contentsof the preliminary second part makes up most of the material in the book. Some of it shouldbe familiar if you have taken a course in algorithms and data structures. Thetake on those topics is a bit different compared to an algorithms course. Wetherefore recommend that you read through the parts even if you feel familiarwith them in particular those on the basic Problem Solving paradigms, force, greedy algorithms, dynamic programming and divide & chapters in this part are structured so that a chapter builds upon only thepreliminaries and previous chapters to the largest extent the end of the book you can find an appendix with some book can also be used to improve your competitive programming parts are unique to competitive programming (in particular Chap-ter 17 on contest strategy).

10 This knowledge is extracted intocompetitivetips:xixiiCONTENTSC ompetitive TipA competitive tip contains some information specific to competitive pro-gramming. These can be safely ignored if you are interested only in theproblem Solving aspect and not the book often refers to exercises from the Kattis online judge. These arenamedKattis Exercise, given as Problem names and Kattis ExerciseProblem Name problemidThe URL of such a Problem C++ code in this book makes use of some preprocessor directives froma template. Even if you are familiar with C++ (or do not wish to learn it) westill recommend that you read through this template (Section ) to betterunderstand the C++ code in the IPreliminaries1 Chapter 1 Algorithms and ProblemsThe greatest technical invention of the last century was probably the digitalgeneral purpose computer.