Algorithms for competetive programmers

Graph Algorithms:

..................................................................................................................................................

Breadth First Search (BFS)

Depth First Search (DFS)

Shortest Path from source to all vertices **Dijkstra**

Shortest Path from every vertex to every other vertex **Floyd Warshall**

Minimum Spanning tree **Prim**

Minimum Spanning tree **Kruskal**

Topological Sort

Johnson’s algorithm

Articulation Points (or Cut Vertices) in a Graph

Bridges in a graph

Dynamic Programming:

..................................................................................................................................................

Coin Change DP

Counting DP

0-1 Knapsack

Longest Common Subsequence

Longest Increasing Subsequence

Minimum Partition

Ways to Cover a Distance

Longest Path In Matrix

Subset Sum Problem

Optimal Strategy for a Game

Bitmask DP

Digit DP

Edit Distance

Expected value/Probability
MCM
N-queen
DP on tree
Binary Search+DP
Non-Classical Problems

String Algorithms
..................................................................................................................................................
Polynomial Hashing/Rolling Hash
Trie
Z-function
Knuth-Morris-Prat
Aho-Corasick
Manacher's Algo
 

Searching And Sorting:

..................................................................................................................................................

Binary Search

Quick Sort

Merge Sort

Order Statistics

KMP algorithm

Rabin karp

Z’s algorithm

Aho Corasick String Matching

Counting Sort

Manacher’s algorithm: Part 1, Part 2 and Part 3

Number theory and Other Mathematical:

..................................................................................................................................................

Prime Numbers and Prime Factorization

Primality Test | Set 1 (Introduction and School Method)

Primality Test | Set 2 (Fermat Method)

Primality Test | Set 3 (Miller–Rabin)

Sieve of Eratosthenes

Segmented Sieve

Wilson’s Theorem

Prime Factorisation

Pollard’s rho algorithm

Modulo Arithmetic Algorithms:

..................................................................................................................................................

Basic and Extended Euclidean algorithms

Euler’s Totient Function

Modular Exponentiation

Modular Multiplicative Inverse

Chinese remainder theorem Introduction

Chinese remainder theorem and Modulo Inverse Implementation

nCr%m and this.

Miscellaneous:

..................................................................................................................................................

Counting Inversions

Counting Inversions using BIT

logarithmic exponentiation

Square root of an integer

Heavy light Decomposition , this and this

Matrix Rank

Gaussian Elimination to Solve Linear Equations

Hungarian algorithm

Link cut

Mo’s algorithm and this

Factorial of a large number in C++

Factorial of a large number in Java+

Russian Peasant Multiplication

Catalan Number

Geometrical and Network Flow Algorithms:

..................................................................................................................................................

Convex Hull

Graham Scan

Line Intersection

Interval Tree

Matrix Exponentiation and this

Maxflow Ford Furkerson Algo and Edmond Karp Implementation

Min cut

Stable Marriage Problem

Hopcroft–Karp Algorithm for Maximum Matching

Dinic’s algo and e-maxx

Data Structures:

..................................................................................................................................................

Binary Indexed Tree or Fenwick tree

Segment Tree (RMQ, Range Sum and Lazy Propagation)

K-D tree (See insert, minimum and delete)

Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)

Tries

Suffix array (this, this and this)

Sparse table

Suffix automata

Suffix automata II

LCA and RMQ