zarif98sjs / advanced-data-structure-and-algorithm

Implementation of all the Data Strucuture & Algorithms learnt during CP and undergrad life

Advanced-Data-Structure-and-Algorithm

---

Algorithm

---

█▀▀ █▀█ ▄▀█ █▀█ █░█   ▀█▀ █░█ █▀▀ █▀█ █▀█ █▄█
█▄█ █▀▄ █▀█ █▀▀ █▀█   ░█░ █▀█ ██▄ █▄█ █▀▄ ░█░

• Graph Traversal
  • BFS
    • Single Source BFS
    • Multi Source BFS
  • DFS
• Single Source Shortest Path (SSSP)
  • Dijkstra
  • Bellman Ford
• All Pair Shortest Path (APSP)
  • Floyd Warshall
  • Johnson
• Minimum Spanning Tree
  • Prim-Jarnik
  • Kruskal
• Cycle
  • Cycle Check
    • Unirected Graph
    • Directed graph
      1. Colouring
      2. Top Sort
  • Odd Cycle existence / Bipartite / Bicolorable check
• Articulation
  • Articulation Point
  • Articulation Bridge
  • Biconnected Components
  • Bridge Tree
• Euler Tour
• DP
  • Subtree Size
• Binary Lifting
  • Lowest Common Ancestor (LCA)
  • Tree Path Min/Max Query
• Network Flow
  • Max Flow
    • Ford Fulkerson
    • Edmonds Karp
    • Dinic
• Techniques
  • Tree Flattening
  • Tree Flattening Euler Tour
  • Rerooting
• Miscellaneous
  • Tree Diameter (BFS / DFS)
  • Topological Sort
  • Strongly Connected Component (SCC)
  • Tree Centroid

█▄░█ █░█ █▀▄▀█ █▄▄ █▀▀ █▀█   ▀█▀ █░█ █▀▀ █▀█ █▀█ █▄█
█░▀█ █▄█ █░▀░█ █▄█ ██▄ █▀▄   ░█░ █▀█ ██▄ █▄█ █▀▄ ░█░

• 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)
  • Prime Factorization in a range [L,R] O( (R-L) * logN ) [Optimized]
• Divisors
  • Number of Divisors
  • Cumulative Sum of Number of Divisors
  • Sum of Divisors
  • Cumulative Sum of Sum of Divisors
• 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

█▀ ▀█▀ █▀█ █ █▄░█ █▀▀
▄█ ░█░ █▀▄ █ █░▀█ █▄█

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

█▀█ █▀▀ █▀▀ █░█ █▀█ █▀ █ █▀█ █▄░█   ▄▀█ █▄░█ █▀▄
█▀▄ ██▄ █▄▄ █▄█ █▀▄ ▄█ █ █▄█ █░▀█   █▀█ █░▀█ █▄▀

█▄▄ ▄▀█ █▀▀ █▄▀ ▀█▀ █▀█ ▄▀█ █▀▀ █▄▀ █ █▄░█ █▀▀
█▄█ █▀█ █▄▄ █░█ ░█░ █▀▄ █▀█ █▄▄ █░█ █ █░▀█ █▄█

• Generate all subsets
• Generate all permutations
• N Queen
  • Easy to Understand
  • Optimized
• Knight's Tour

█▄▄ █ ▀█▀
█▄█ █ ░█░

• Bit Manipulation
• Builtin Functions

█▀ █▀▀ ▄▀█ █▀█ █▀▀ █░█  
▄█ ██▄ █▀█ █▀▄ █▄▄ █▀█  

▀█▀ █▀▀ █▀▀ █░█ █▄░█ █ █▀█ █░█ █▀▀
░█░ ██▄ █▄▄ █▀█ █░▀█ █ ▀▀█ █▄█ ██▄

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

 

---

Data Structure

---

• Disjoint Set

• Fenwick Tree / Binary Indexed Tree

  • 1D BIT

    point update : O(logN)
    prefix sum array update : O(logN)

    • Point Update , Range Query , lower_bound , upper_bound

      lower_bound , upper_bound
      --------------------------
      binary search  - O( (logN)^2 )
      binary lifting - O(logN)

    • Range Update , Point Query
  • 2D BIT

    point update : O( (logN)^2 )
    2D prefix sum array update : O( (logN)^2 )

    • Point Update , Range Query
    • Range Update , Point Query

• Recursive Segment Tree

  • Non Lazy (Point Update , Range Query)

    build : O(N) 
    update , query : O(logN)

    • Range Sum ( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
    • Maximum Prefix Sum & Maximum Suffix Sum & Maximum Contiguous SubArray Sum
  • Lazy (Range Update , Range Query)

    build : O(N) 
    update , query : O(logN)

    • Range Assignment Update , Range Sum Query
    • Range Increment Update , Range Sum Query
    • Range Increment Update , RMQ
    • Range Flip Update , Range Sum 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 )

• Iterative Segment Tree

  • Non Lazy

    build : O(N) 
    update , query : O(logN)

    • Point Update , Range Query
      ( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
    • Range Update , Point Query

• Implicit Segment Tree

• AVL Tree

• Red Black Tree

• Treap

  • Classic Implementation
  • Implicit Treap
    • Range Update , Range Query
    • Cut Array Portions and Swap
    • Range Delete or Insert , Palindrome Check

• Hash Table

  • Separate Chaining
  • Open Addressing (Double Hashing , Custom Probing)

• Sparse Table

  • Range Sum Query : O(logN)
  • RMQ : O(1)

• Sweep Line Algorithm

• Mo's Algorithm (Square Root Decomposition)

  Total Complexity : O ( (N+Q)F * sqrt(N) )
  where O(F) is the complexity of add and remove function

  • Range Sum Query
  • Range Mode (Highest Frequency) Query
  • Range Mode Sum (Sum of all element with highest frequency) Query
  • Range Number of Distinct Elements 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

 

---

Dynamic Programming

---

• LCS Variant
  • Longest Common Subsequence
  • Longest Palindromic Subsequence
  • Longest Repeated Subsequence
  • Levenshtein / Edit Distance
  • Shortest Common Supersequence
• LIS Variant
  • Longest Increasing Subsequence
    • O(N^2)
    • O( NlogN ) Binary Search
    • O( NlogN ) Segment Tree
  • Longest Bitonic Subsequence
  • Increasing Subsequence with Maximum Sum
  • Longest Increasing Index-Dividing Subsequence
  • Longest Common Increasing Subsequence
    • O( N^3 )
    • O( N^2 )
• 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

 

---

Miscellaneous

---

• Operator Overloading for sorting / STL Data Structure

  • Using Comparator functions / structure
  • Overloading < operator
  • Overloading > operator

• Coordinate Compression

• BIG Integer Library

• Integer Root

  • Square Root (Binary Search) (Modifiable to nth Root)
  • Fast Square & Cube Root

• Geometry Template

  • Point & Line
  • Rectangle

---

If you like my work, you can also support me by buying me a cup of coffee!

---

Md. Zarif Ul Alam

Computer Science & Engineering Department , BUET