shivaguntuku / top10algoritms

Top 10 Algorithms and Data Structures for Competitive Programming

Top10algoritms

Top 10 Algorithms and Data Structures for Competitive Programming

###Graph Algorithms

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 - P
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
10. Manacher’s algorithm: Part 1, Part 2 and Part 3

##Number theory and Other Mathematical

####Prime Numbers and Prime Factorization

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

####Modulo Arithmetic Algorithms

1. Basic and Extended Euclidean algorithms
2. Euler’s Totient Function
3. Modular Exponentiation
4. Modular Multiplicative Inverse
5. Chinese remainder theorem and Modulo Inverse Implementation
6. nCr%m

####Miscellaneous Algorithms

1. Counting Inversions
2. Counting Inversions using BIT
3. logarithmic exponentiation
4. Square root of an integer
5. Heavy light Decomposition and this
6. Matrix Rank
7. Hungarian algorithm
8. Link cut
9. Mo’s algorithm and this
10. Russian Peasant Multiplication
11. Catalan Number

###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

###Data Structures

1. Binary Indexed Tree or Fenwick tree
2. Segment Tree (RMQ, Range Sum and Lazy Propagation)
3. K-D tree (See insert, minimum and delete)
4. Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
5. Tries
6. Suffix array (this, this and this)
7. Sparse table
8. Suffix automata
9. Suffix automata II
10. LCA and RMQ

Source @ http://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/