Top 10 Algorithms and Data Structures for Competitive Programming

 

Topics :

1. Graph algorithms
2. Dynamic programming
3. Searching and Sorting:
4. Number theory and Other Mathematical
5. Geometrical and Network Flow Algorithms
6. Data Structures

Graph:

1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Shortest Path from source to all vertices **Dijkstra**
4. Shortest Path from every vertex to every other vertex **Floyd Warshall**
5. Minimum Spanning tree **Prim**
6. Minimum Spanning tree **Kruskal**
7. Topological Sort
8. Johnson’s algorithm
9. Articulation Points (or Cut Vertices) in a Graph
10. Bridges in a graph

Dynamic Programming

1. Longest Common Subsequence
2. Longest Increasing Subsequence
3. Edit Distance
4. Minimum Partition
5. Ways to Cover a Distance
6. Longest Path In Matrix
7. Subset Sum Problem
8. Optimal Strategy for a Game
9. 0-1 Knapsack Problem
10. Assembly Line Scheduling

Searching And Sorting

1. Binary Search
2. Quick Sort
3. Merge Sort
4. Order Statistics
5. KMP algorithm
6. Rabin karp
7. Z’s algorithm
8. Aho Corasick String Matching
9. Counting Sort

Number theory and Other Mathematical

Prime Numbers and Prime Factorization

1. Primality Test | Set 1 (Introduction and School Method)
2. Primality Test | Set 2 (Fermat Method)
3. Primality Test | Set 3 (Miller–Rabin)
4. Sieve of Eratosthenes
5. Segmented Sieve
6. Wilson’s Theorem
7. Prime Factorisation
8. Pollard’s rho algorithm

 Geometrical and Network Flow Algorithms

1. Convex Hull
2. Graham Scan
3. Line Intersection
4. Interval Tree
5. Matrix Exponentiation
6. Maxflow Ford Furkerson Algo and Edmond Karp Implementation
7. Min cut
8. Stable Marriage Problem
9. Hopcroft–Karp Algorithm for Maximum Matching
10. Dinic’s algo and e-maxx