Top 10 Algorithms and Data Structures for Competitive Programming

IMP Algorithm
Top 10 Algorithms and Data Structures for Competitive Programming

In this post “Important top 10 algorithms and data structures for competitive coding “.
Topics :

    Graph algorithms
    Dynamic programming
    Searching and Sorting:
    Number theory and Other Mathematical
    Geometrical and Network Flow Algorithms
    Data Structures

competitive-programming

The below links cover all most  important algorithms and data structure topics:


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

All Graph Algorithms


Dynamic Programming

    Longest Common Subsequence
    Longest Increasing Subsequence
    Edit Distance
    Minimum Partition
    Ways to Cover a Distance
    Longest Path In Matrix
    Subset Sum Problem
    Optimal Strategy for a Game
    0-1 Knapsack Problem
    Assembly Line Scheduling

All DP Algorithms

 


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

All Articles on Searching, Sorting and Pattern Searching.


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

All Articles on Mathematical Algorithms


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

All Articles on Geometric Algorithms


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