100 Algorithms in Competitive Programming

Competitive Programming
1

Algorithms

1. Basic Sorting Algorithms

  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quick Sort
  6. Heap Sort
  7. Counting Sort
  8. Radix Sort
  9. Bucket Sort

2. Searching Algorithms

  1. Linear Search
  2. Binary Search
  3. Jump Search
  4. Interpolation Search
  5. Exponential Search
  6. Ternary Search

3. Graph Algorithms

  1. Depth-First Search (DFS)
  2. Breadth-First Search (BFS)
  3. Dijkstra’s Shortest Path Algorithm
  4. Bellman-Ford Algorithm
  5. Floyd-Warshall Algorithm
  6. Kruskal’s Minimum Spanning Tree (MST)
  7. Prim’s Minimum Spanning Tree (MST)
  8. Topological Sort
  9. Kahn’s Algorithm for Topological Sorting
  10. Tarjan’s Algorithm for Strongly Connected Components
  11. Kosaraju’s Algorithm for Strongly Connected Components
  12. Ford-Fulkerson Algorithm for Maximum Flow
  13. Edmonds-Karp Algorithm (BFS-based Maximum Flow)
  14. Dinic’s Algorithm (Maximum Flow)
  15. Hopcroft-Karp Algorithm (Maximum Bipartite Matching)
  16. Bellman-Ford Algorithm for Negative Cycles

4. Dynamic Programming

  1. Fibonacci Sequence (DP)
  2. Knapsack Problem (0/1 Knapsack)
  3. Longest Common Subsequence
  4. Longest Increasing Subsequence
  5. Matrix Chain Multiplication
  6. Edit Distance
  7. Coin Change Problem
  8. Subset Sum Problem
  9. Partition Problem
  10. Rod Cutting Problem
  11. Unbounded Knapsack Problem
  12. Longest Palindromic Subsequence

5. Greedy Algorithms

  1. Activity Selection Problem
  2. Fractional Knapsack Problem
  3. Huffman Coding
  4. Kruskal’s Algorithm for MST
  5. Prim’s Algorithm for MST
  6. Job Sequencing Problem
  7. Optimal Merge Pattern

6. Backtracking

  1. N-Queens Problem
  2. Sudoku Solver
  3. Subset Sum Problem
  4. Permutations and Combinations
  5. Hamiltonian Path/Circuit
  6. Knight’s Tour Problem
  7. Graph Coloring Problem

7. Graph Theory Algorithms

  1. Eulerian Path and Circuit
  2. Hamiltonian Path and Circuit
  3. Articulation Points (Cut Vertices)
  4. Bridges in Graphs (Cut Edges)
  5. Bipartite Graph Check
  6. Maximum Bipartite Matching
  7. Strongly Connected Components (SCCs)
  8. Bridge-Finding Algorithm

8. Number Theory Algorithms

  1. Sieve of Eratosthenes (Prime Generation)
  2. Greatest Common Divisor (GCD) - Euclidean Algorithm
  3. Least Common Multiple (LCM)
  4. Modular Arithmetic
  5. Fast Exponentiation (Exponentiation by Squaring)
  6. Modular Inverse (Extended Euclidean Algorithm)
  7. Chinese Remainder Theorem
  8. Prime Factorization
  9. Miller-Rabin Primality Test
  10. Fermat’s Little Theorem

9. Data Structures Algorithms

  1. Segment Tree (with Lazy Propagation)
  2. Fenwick Tree (Binary Indexed Tree)
  3. Trie Operations
  4. Union-Find Data Structure (Disjoint Set Union)
  5. Splay Trees
  6. Treap (Randomized Binary Search Tree)
  7. AVL Trees
  8. Red-Black Trees
  9. Skip Lists

10. String Algorithms

  1. KMP String Matching Algorithm
  2. Rabin-Karp Algorithm
  3. Z Algorithm
  4. Suffix Array Construction
  5. Suffix Tree Construction
  6. Longest Common Prefix (LCP) Array
  7. Manacher’s Algorithm (Longest Palindromic Substring)
  8. Aho-Corasick Algorithm (Multi-pattern String Matching)
  9. Edit Distance
  10. String Hashing

11. Computational Geometry Algorithms

  1. Convex Hull (Graham Scan, Jarvis March)
  2. Line Intersection
  3. Point in Polygon
  4. Polygon Area Calculation
  5. Sweep Line Algorithm
  6. Segment Intersection