README.md

Contents

1. data structures

• union find disjoint sets
• segment tree
  • range minimum query
  • merge sort tree
• fenwick tree
• sparse table
  • range min/max query
  • range sum query
• sorting
  • merge sort
  • selection sort
  • bubble sort

---

2. problem solving paradigms

---

3. mathematics

• combinatorics
  • fibonacci numbers
    • pisano periodic sequence
• number theory
  • prime generation
    • simple sieve of eratosthenes
    • wheel sieve
    • segmented sieve
    • linear sieve
  • integer factorization
    • extended wheel factorization
    • least prime factorization
  • extended euclid: solving linear diophantine equation
  • modified sieve
    • euler phi
    • mobius
  • primality tests
    • miller-rabin test
  • functions involving prime factors
    • euler totient function
    • mobius function
    • phi factorial
• probability theory
• game theory
• cycle finding
• big integer class
• ad-hoc mathematics problems
  • stable matching
    • the stable marriage problem

---

4. graph theory

• graph traversal
  • depth first search
  • breadth first search
  • finding articulation points and bridges
    • articulation points and bridges
    • bi-connected components
  • finding strongly connected components
    • tarjan
    • directed cyclic graph into dag
  • topological sort
    • topological sort
    • kahn's algorithm
  • applications
    • connected components
    • flood fill
    • bi-partite graph check
    • edge classification
    • adjacency list
    • cycle detection (directed graph)
    • cycle detection (undirected graph)
    • minimum vertex cover
• minimum spanning tree (mst)
  • kruskal's algorithm
    • kruskal
  • prim's algorithm
• single_source shortest paths (sssp)
  • unweighted graph
    • single source shortest path
    • single source shortest path on grids
    • shortest cycle
    • restoring the path
  • weighted graph
    • dijkstra on sparse graphs
    • dijkstra on dense graphs
    • dijkstra on grids
    • dijkstra on -ve weight edges
    • special case (0-1 bfs)
      • single pair shortest path
      • single pair shortest path on grids
  • graph with negative weight cycle
    • bellman_ford's algorithm
    • shortest path faster algorithm (spfa)
• all pairs shortest paths (apsp)
  • floyd_warshall's algorithm
• special graphs
  • directed acyclic graph (dag)
  • tree
    • tree diameter
    • lowest common ancestor (lca)
      • lca (eulerian tour and rmq)
      • kth ancestor and lca (binary lifting)
  • eulerian graph
    • eulerian tour of tree
  • bipartite graph
• network flow

---

5. string processing

• trie
• knuth morris pratt algorithm (kmp)
• rabin karp
• manacher

---

6. geometry

• types
• convex hull

---

7. more advanced topics

• advanced search techniques
  • informed search: a star algorithm
• range queries
  • mo's algorithm
  • square root decomposition

---

8. rare topics

---

9. miscellaneous

• pseudo random number generator
• stress test
• fast input/output
• modular calculations
• double comparison
• overloaded operators << and >> to accept an 128bit integer (i/o)
• policy based data structures
• contest template - c++
• my debugging tools
• binary gcd & lcm