Recently Springer made some good books on maths free to download.
Competitive programming strategies are useful for many data science interviews and they help to improve your maths foundations. There are not many books on this subject (although there are many good websites and YouTube resources).
So, I hope you find this book useful
From the book
- Competitive programming combines two topics: the design of algorithms and the implementation of algorithms.
- Design of Algorithms The core of competitive programming is about inventing efficient algorithms that solve well-defined computational problems.
- The design of algorithms requires problem solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and new insights.
- Mathematics plays an important role in competitive programming. Actually, there are no clear boundaries between algorithm design and mathematics.
- The most common language for the implementation of competitive algorithms is C++
The book contents are
Programming Techniques
Language Features
Input and Output
Working with Numbers
Shortening Code
Recursive Algorithms
Generating Subsets
Generating Permutations
Backtracking
Bit Manipulation
Bit Operations
Representing Sets
Efficiency
Time Complexity
Calculation Rules
Common Time Complexities
Estimating Efficiency
Formal Definitions
Examples
Maximum Subarray Sum
Two Queens Problem
Sorting and Searching
Sorting Algorithms
Bubble Sort
vii
Merge Sort
Sorting Lower Bound
Counting Sort
Sorting in Practice
Solving Problems by Sorting
Sweep Line Algorithms
Scheduling Events
Tasks and Deadlines
Binary Search
Implementing the Search
Finding Optimal Solutions
Data Structures
Dynamic Arrays
Vectors
Iterators and Ranges
Other Structures
Set Structures
Sets and Multisets
Maps
Priority Queues
Policy-Based Sets
Experiments
Set Versus Sorting
Map Versus Array
Priority Queue Versus Multiset
Dynamic Programming
Basic Concepts
When Greedy Fails
Finding an Optimal Solution
Counting Solutions
Further Examples
Longest Increasing Subsequence
Paths in a Grid
Knapsack Problems
From Permutations to Subsets
Counting Tilings
Graph Algorithms
Basics of Graphs
Graph Terminology
Graph Representation
Graph Traversal
Depth-First Search
viii Contents
Breadth-First Search
Applications
Shortest Paths
Bellman–Ford Algorithm
Dijkstra’s Algorithm
Floyd–Warshall Algorithm
Directed Acyclic Graphs
Topological Sorting
Dynamic Programming
Successor Graphs
Finding Successors
Cycle Detection
Minimum Spanning Trees
Kruskal’s Algorithm
Union-Find Structure
Prim’s Algorithm
Algorithm Design Topics
Bit-Parallel Algorithms
Hamming Distances
Counting Subgrids
Reachability in Graphs
Amortized Analysis
Two Pointers Method
Nearest Smaller Elements
Sliding Window Minimum
Finding Minimum Values
Ternary Search
Convex Functions
Minimizing Sums
Range Queries
Queries on Static Arrays
Sum Queries
Minimum Queries
Tree Structures
Binary Indexed Trees
Segment Trees
Additional Techniques
Tree Algorithms
Basic Techniques
Tree Traversal
Calculating Diameters
All Longest Paths
Contents ix
Tree Queries
Finding Ancestors
Subtrees and Paths
Lowest Common Ancestors
Merging Data Structures
Advanced Techniques
Centroid Decomposition
Heavy-Light Decomposition
Mathematics
Number Theory
Primes and Factors
Sieve of Eratosthenes
Euclid’s Algorithm
Modular Exponentiation
Euler’s Theorem
Solving Equations
Combinatorics
Binomial Coefficients
Catalan Numbers
Inclusion-Exclusion
Burnside’s Lemma
Cayley’s Formula
Matrices
Matrix Operations
Linear Recurrences
Graphs and Matrices
Gaussian Elimination
Probability
Working with Events
Random Variables
Markov Chains
Randomized Algorithms
Game Theory
Game States
Nim Game
Sprague–Grundy Theorem
Advanced Graph Algorithms
Strong Connectivity
Kosaraju’s Algorithm
SAT Problem
Complete Paths
Eulerian Paths
x Contents
Hamiltonian Paths
Applications
Maximum Flows
Ford–Fulkerson Algorithm
Disjoint Paths
Maximum Matchings
Path Covers
Depth-First Search Trees
Biconnectivity
Eulerian Subgraphs
Geometry
Geometric Techniques
Complex Numbers
Points and Lines
Polygon Area
Distance Functions
Sweep Line Algorithms
Intersection Points
Closest Pair Problem
Convex Hull Problem
String Algorithms
Basic Topics
Trie Structure
Dynamic Programming
String Hashing
Polynomial Hashing
Applications
Collisions and Parameters
Z-Algorithm
Constructing the Z-Array
Applications
Suffix Arrays
Prefix Doubling Method
Finding Patterns
LCP Arrays
Additional Topics
Square Root Techniques
Data Structures
Subalgorithms
Integer Partitions
Mo’s Algorithm
Contents xi
Segment Trees Revisited
Lazy Propagation
Dynamic Trees
Data Structures in Nodes
Two-Dimensional Trees
Treaps
Splitting and Merging
Implementation
Additional Techniques
Dynamic Programming Optimization
Convex Hull Trick
Divide and Conquer Optimization
Knuth’s Optimization
Miscellaneous
Meet in the Middle
Counting Subsets
Parallel Binary Search
Dynamic Connectivity
Appendix A: Mathematical Background
link to download https://link.springer.com/book/10.1007/978-3-319-72547-5
