Alba D., Leal J. Algorithms: For Competitive Programming

Independently published, 2021. — 371 p. — ISBN B08V51PVCX.Preparing for your incoming programming contest or coding interview? This book contains detailed explanations and source code for algorithms used in competitive programing. Written by software engineers with experience in programming competitions and developing high scalable systems for some of the biggest tech companies. It covers algorithms in the areas of Graph Theory, Number Theory, Combinatorics, Dynamic Programming, Geometry, and more. Competitive programming is frequently associated with algorithms, but an algorithm is just a set of instructions that are given to the computer to solve a specific problem that has already been solved in the head of the programmer. The goal of this book is to provide two things for each algorithm, a brief description of how it works and a source code that implements the theory behind the algorithm. Each section contains exercises and their respective solutions. Also the appendices contain problems with non-trivial solutions that we have selected to show the reader how sometimes simple algorithms can solve complex problems, and also how simple problems may require a complex solution. The source code of the exercises and other algorithms in this book can be found in the GitHub page: https://github.com/Cheetos/afcp. We have written this book because of our passion for algorithms, its content comes from trainings for programming competitions, from coaching and mentoring others, from failures and successes on tech interviews, from our experience in the tech industry, etc. We hope that you find this book useful for your objectives, and that you enjoy reading it as much as we enjoyed writing it.Programming Contests
Coding Interviews
Online Judges
C and C++
Chapter Notes
Fundamentals
Recursion
Memoization
Algorithm Analysis
Asymptotic Notations
Master Theorem
P and NP
Bitwise Operations
AND (&) operator
OR (|) operator
XOR operator
Two’s complement
Chapter Notes
Exercises
Data Structures
Linear Data Structures
Stack
Queue
Linked List
Trees
Tree Traversal
Heap
Binary Search Tree (BST)
AVL Tree
Segment Tree
Binary Indexed Tree (BIT)
Trie
Standard Template Library (STL) C++
Unordered Set
Ordered Set
Unordered Map
Ordered Map
Stack
Queue
Priority queue
Chapter Notes
Exercises
Sorting Algorithms
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Merge Sort
Heap Sort
Sorting With the algorithm Library
Overloading operator <
Adding a function to sort
Chapter Notes
Exercises
Divide and Conquer
Binary Search
Binary Exponentiation
Closest Pair of Points
Polynomial Multiplication (FFT)
Range Minimum Query (RMQ)
Chapter Notes
Exercises
Dynamic Programming
Longest Increasing Sub-sequence (LIS)
Longest Increasing Subsequence with Binary Search
Longest Common Sub-sequence (LCS)
Levenshtein Distance (Edit Distance)
Knapsack Problem
Maximum Sum in a Sequence
Rectangle of Maximum Sum
Optimal Matrix Multiplication
Coin Change Problem
Chapter Notes
Exercises
Graph Theory
Graph Representation
Adjacency Matrix
Adjacency List
Graph Traversal
DFS
BFS
Topological Sort
Disjoint Sets
Union-Find
Shortest Paths
Dijkstra’s Algorithm
Bellman-Ford
Floyd-Warshall
A*
Strongly Connected Components
Tarjan’s Algorithm
Kosaraju’s Algorithm
Minimum Spanning Tree
Kruskal’s Algorithm
Prim’s Algorithm
Maximum Bipartite Matching
Flow Network
Ford-Fulkerson Algorithm
Chapter Notes
Exercises
Geometry
Point Inside a Polygon
Point in Convex Polygon
Point in Polygon
Point Inside a Triangle
Area of a Polygon
Line Intersection
Horner’s Rule
Centroid of a Convex Polygon
Convex Hull
Andrew’s Monotone Convex Hull Algorithm
Graham’s Scan
Chapter Notes
Exercises
Number Theory and Combinatorics
Prime Numbers
Sieve of Eratosthenes
Prime Number Generator
Euler’s Totient Function
Sum of Divisors
Number of Divisors
Modular Arithmetic
Euclidean Algorithm
Extended Euclidean Algorithm
Base Conversion
Sum of Number of Divisors
Combinations
Pascal’s Triangle
Catalan Numbers
Josephus
Pigeon-Hole Principle
Chapter Notes
Exercises
String Manipulation
Next Permutation
Knuth-Morris-Pratt Algorithm (KMP)
Manacher’s Algorithm
Chapter Notes
Exercises
Solution to Exercises
Fundamentals
Data Structures
Sorting Algorithms
Divide and Conquer
Dynamic Programming
Graph Theory
Geometry
Number Theory and Combinatorics
String Manipulation
A Recursion and Bitwise
The 8-Queen problem
Vacations
B Data Structures Problems
Find two numbers whose sum is k
Shunting-yard Algorithm
Find the median
C Sorting Problems
Marching in the school
How Many Swaps?
Closest K Points to the Origin?
D Divide and Conquer Problems
Polynomial Product
Wi-Fi Connection
E Graph Theory Problems
Minmax and Maxmin
Credit Card (minmax)
LufeMart (maxmin)
Money Exchange Problem
F Number Theory Problems
Sum of Consecutive Numbers
Two Queens in Attacking Positions
Example. Sum of GCD’s
Find B if LCM(A,B) = C
Last Non Zero Digit in n!