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.

2 Statements .. Loops .. Loops .. Structures .. Arrays .. The Preprocessor .. Template .. Additional Exercises .. Chapter Notes .. 503 The C++ Standard .. End of File .. 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.

3 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 .. Problems .. Common Subsequence .. Cover .. Notes .. 16810 Divide and Inductive Constructions.

4 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.

5 219 CONTENTSvii13 Maximum Flow Networks .. Edmonds-Karp .. Augmenting Paths .. Finding Augmenting Paths .. 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.

6 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 .. 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.

7 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.

8 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.

9 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 . 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.

10 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.