List of basic algorithms and data structures for algorithmic programming competitions (International Olympiad in Informatics (IOI), ACM International Collegiate Programming Competition (ICPC), Google Code Jam, Facebook Hacker Cup, etc.).
In the past, this list has been quite useful for solving algorithmic programming challenges on online judges like the Sphere Online Judge (SPOJ) and competitions.
Most of this has been coded during high-school (2016-2018) while preparing for the IOI. Consider this a disclaimer about the coding style. I will try to improve the code whenever I have some free time. Bullet-points that are not highlighted below have not been added yet.
If you see any errors or would like to make some improvements, please feel free to set an issue, or even better, make a pull request.
The code is licensed under the MIT License, free to use, have fun!
- Bignum (addition, subtraction, multiplication, division)
- Prime Factorization O(sqrt(n))
- Prime Number Generator (Sieve of Eratosthenes)
- GCD (Greatest Common Divisor)
- LCD (Lowest Common Multiple)
- Linear Congruence (Extended GCD)
- Miller-Rabin Primality Test
- All Permutation
- All Subsets
- Next Permutation (alphabetically higher)
- DFS (Depth-First Search)
- BFS (Breadth-First Search)
- Connected Components
- Dijkstra's Algorithm (One Way Shortest Path)
- Prim's Algorithm (Minimum Spanning Tree)
- Kruskal's Algorithm (Minimum Spanning Tree)
- Floyd-Warshall (All Way Shortest Path)
- Toposort (Topological Sort)
- ArticFind (Find all Articulation Points), O(E)
- Ford-Fulkerson's Algorithm with Capacity Scaling (Maxflow/Mincut)
- Dinic's Algorithm (Maxflow/Mincut)
- Edmonds-Karp's Algorithm (Maxflow/Mincut)
- Hierholzer's Algorithm (Euler Cycle detection)
- Bellman Ford (for negative weights)
- Bipartite Matching
- Graham's Scan Algorithm (Convex Hull)
- Closest Pair of Points (Sweep Line)
- Line-Line Intersection
- Segment-Segment Intersection
- Area of Polygon
- Line-Point Distance
- Point-Segment Distance
- Circle from Three Points
- Reflection
- Rotation
- Area of a Triangle (three points)
- Bentley-Ottman's Algorithm (Sweep Line, finding all intersections of multiple line segments)
- Shamos-Hoey Algorithm (checking if there is an intersection given multiple line segments)
- Crossing Number (resp. Winding Number, method to check whether a point is inside a simple polygon (resp. non-simple polygon))
- Queue
- Stack
- Singly Linked List
- Binary Indexed Tree (BIT)
- 2D Binary Indexed Tree (2D BIT)
- Binary Search Tree (BST)
- Priority-Queue
- Heap
- Segment Tree
- Dictionary (STL Map)
- Set (STL Set)
- Suffix Array (resp. Suffix Sorting, determine if string is a subseq. of another string)
- Union-Find (Disjoint-Set Data Structure)
- Doubly Linked List
- STL Vector
- Trie
- Hash Table
- Suffix Tree
A selection of solutions to fairly standard DP problems.
- Edit Distance
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS), O(nlogn)
- Matrix Chain Multiplication (MCM)
- Maximum Empty Rectangle (MER)
- Range Minimum Query, Sparse Table (RMQ)
- Stable Marriage Problem
- Binomial Coefficient Solver
- String Handling (in general)
- Knuth Morris Pratt (String Search)
- Majority Vote
- Inclusion/Exclusion (using bit tricks)