• Graph Traversal
  • BFS
    • Single Source BFS
    • Multi Source BFS
  • DFS
    • Simple DFS
    • Cycle Check (Undirected Graph)
    • Cycle Check (Directed Graph)
    • Bipartite / Bicolorable / Odd Cycle existence check
    • Subtree Size
• Single Source Shortest Path (SSSP)
  • Dijkstra
  • Bellman Ford
• All Pair Shortest Path (APSP)
  • Floyd Warshall
  • Johnson
• Minimum Spanning Tree
  • Prim-Jarnik
  • Kruskal
• Articulation
  • Articulation Point
  • Articulation Bridge
  • Biconnected Components
  • Bridge Tree
• Miscellaneous
  • Lowest Common Ancestor (LCA)
  • Topological Sort
  • Strongly Connected Component (SCC)

• Power & Modulus
  • Power
  • Big Mod
  • Inverse Mod
• Extended Euclidean Algorithm
• nCr
• Sieve of Eratosthenes
  • General Sieve : O( N log(logN) ) , Memory : O(N)
  • Bit Sieve : O( N log(logN) ) , Memory : N bit
  • Segmented Sieve : O( (R-L+1) log(logR) + sqrt(R) log(log(sqrt(R))) ) , Memory : O(R-L+1)
• Prime Factorization
  • Using all primes : O( (sqrt(N)/log(sqrt(N)) * logN )
  • Using only smallest prime factor : O(logN)
• Divisors
  • Number of Divisors
  • Cumulative Sum of Number of Divisors
  • Sum of Divisors
  • Cumulative Sum of Sum of Divisors
  • All Prime Divisors : O( sqrt (N) )
• Euler Totient
• Linear Diophantine
  • 2 Variable
  • 3 Variable
  • Number of solutions in a range
• Highest Composite Number
• Factorials
  • Number of digits in N factorial
  • Prime Factorization of N Factorial O(N*log(N))
  • Find the first K digits of N!
• Chinese Remainder Theorem

• Suffix Array : O( NlogN )
• Longest Common Prefix (LCP) Array Construction : O(N)
• Prefix Function (KMP ALgorithm) : O(N)

• Binary Search
  • lower_bound , upper_bound implementation
  • Solve Equation
  • Meet In The Middle

• Disjoint Set
• Binary Indexed Tree / Fenwick Tree
  • 1D BIT
    • Point Update , Range Query , lower_bound , upper_bound
      update , query : O(logN)
      lower_bound , upper_bound : binary search - O( (logN)^2 ) , binary lifting - O(logN)
    • Range Update , Point Query
      update , query : O(logN)
  • 2D BIT
    • Point Update , Range Query
• Segment Tree
  • Range Sum
    • Point Update , Range Query
      ( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
      build : O(n)
      update , query : O(logN)
    • Range Update , Range Query (Lazy Propagation)
  • Maximum Prefix Sum & Maximum Suffix Sum & Maximum Contiguous SubArray Sum
    • Point Update , Range Query
• Merge Sort Tree
  • Range Query
    build : O( NlogN )
    query : O( (logN)^2 )
    memory : O( NlogN )
  • Point Update , Range Query
    build : O( N (logN)^2 )
    update , query : O( (logN)^2 )
    memory : O( NlogN )
• Sweep Line Algorithm
• Mo's Algorithm (Square Root Decomposition)
  • Range Sum Query
  • Range Mode (Highest Frequency) Query
• Suffix Array
  • O( N^2 logN )
  • O( N (logN)^2 )
  • O( NlogN )
  • O( NlogN ) optimized
• Priority Queue
• STL
  • Set
  • Map
• Policy Based Data Structure
  • Set
  • Multiset
    • Implementation 1 (erase doesn't work)
    • Implementation 2

• LCS Variant
  • Longest Common Subsequence
  • Longest Palindromic Subsequence
  • Longest Repeated Subsequence
  • Levenshtein / Edit Distance
  • Shortest Common Supersequence
• LIS Variant
  • Longest Increasing Subsequence
  • Longest Bitonic Subsequence
  • Increasing Subsequence with Maximum Sum
  • Longest Increasing Index-Dividing Subsequence
• Coin Change
  • Coin Change (Minimum number of coins to make a sum)
  • Coin Change (Number of ways to make a sum)
  • LightOj 1079 (Just Another Robbery)
• Matrix Variant
  • Largest Square Matrix with all 1's
  • Minimum Cost Matrix Path (Top Left cell to Bottom Right cell)
  • Number of paths in a matrix with certain cost (Top Left cell to Bottom Right cell)
  • Longest Sequence formed by adjacent numbers in a matrix
  • 2 Way Prefix Sum (LightOj)
• Knapsack Variant
  • 0-1 Knapsack
  • Partition Problem
  • Minimum Sum Partition Problem
• Digit DP Variant
  • Number of zeros (LightOj)
  • Odd Sum Even Sum (SPOJ)
  • Digit Min Max Scores (HackerRank)
  • Adjacent 1 Scores in binary (LightOj)
  • Divisibility check by Digit Sum (LightOj)
  • Digit Sum (SPOJ)
  • Encoding (CodeChef)
• Bitmask DP
  • Bitmask DP 1 [ LightOj 1011 (Marriage Ceremonies) ]
  • Bitmask DP 2 [ LightOj 1018 (Brush IV) ]
  • Bitmask DP 3 [ LightOj 1037 (Agent 47) ]
  • Bitmask DP 4 [ LightOj 1057 (Collecting Gold) ]
• Miscellaneous
  • N-digit binary strings without any consecutive 1’s

• Operator Overloading for sorting / STL Data Structure

  • Using Comparator
  • Overloading < operator
  • Overloading > operator

• Geometry Template

  • Point & Line
  • Rectangle

Computer Science & Engineering Department , BUET