Data Structures and Algorithms for Online Programming Contest
Dynamic Programming
- Coin Change and variants
- Knapsack Problem and variants
- Matrix Chain Multiplication
- Longest Increasing Subsequence( O(n^2) )
- Longest Increasing Subsequence( O(nlogn) )
- Travelling Salesman Problem
- Maximum Sum Subarray( O(n^4) and O(n^3) )
- Kadane Algorithm
- Maximum Sum Subarray using Kadane( O(n^3) )
- Optimal Binary Search Tree
- Subset Sum
- Catalan Number
- DAG Minimum Path
- Minimum Cost Path
- Digit Dp I
- Digit Dp II
- Digit Dp III
- Digit Dp IV
Backtracking
Greedy Algorithm
String Algorithm
- Aho-Corasick Algorithm
- Knuth-Morris-Pratt’s Algorithm
- Rabin Karp Pattern Searching
- Z Algorithm
- Finite Automata Pattern Searching
- Trie (Prefix/Radix Tree)
- Longest Common Subsequence
- Edit Distance
- Longest Palindromic Subsequence
- Suffix Array
- Longest Common Prefix
- Minimum Expression
- Suffix Automata
Graph Theory
- Floyd Warshall’s
- Loop Detection
- Topological Sort
- Strongly Connected Component (Kosaraju)
- Lowest Common Ancestor(sparse table)
- Articulation Point
- Bridge
- Breadth First Search
- Dijkstra
- Bellman Ford's
- Kruskal Minimum Spanning Tree
- Minimum Vertex Cover
- Maximum Flow (Edmonds Karp’s) I
- Maximum Flow (Edmonds Karp’s) II
- Maximum Bipartite Matching
- Stable Marriage Problem
- Heavy Light Decomposition
Mathematics
- Power Function(Big mod)
- Modular Mutiplicative Inverse(using Big mod)
- Prime(Sieve of Erathonesis)
- Segmented Sieve of Erathonesis
- Prime factorization(using Sieve)
- Prime factorization
- Primality Test(School method)
- Miller–Rabin Primality Test
- Euler Totient (Phi Function)
- Extended Euclid
- Linear Diophatine Equation
- Modular Mutiplicative Inverse(using Extended Euclid)
- Matrix Exponentiation
- Floyd Cycle Finding Algorithm
- Big Integer
- Josephus Recurrence
- Fast Fourier Transform
Combinotorics
Game Theory
- Game Tree(Memorization)
- Nim
- Misère Nim
- Nimble Nim
- Poker Nim
- Prime Power Nim
- Spagrue Grundy Problem
- Grundy Variant: Zero Nim Game
- Grundy Variant: Coins on Chessboard
- Green HackenBush(Colon Principle)
Binary Search
Data Structure
- Singly Linked List
- Doubly Linked List
- Vector
- Stack
- Queue
- List
- Hashtable
- HashMap
- HashSet
- Union Find(Disjoint Set)
- Binary Search Tree
- Segment Tree
- Segment Tree (Lazy Propagation)
- 2D Segment Tree (Quad tree)
- Binary Indexed Tree
- 2D Binary Indexed Tree
- (AVL Tree) Self Balanced BST
- (Splay Tree) Self Balanced BST
- Ternary Search Tree
- Heap (Min)
Computational Geometry
- Computational Geometry Template
- Convex Hull (Jarvis’s Algorithm or Wrapping)
- Convex Hull (Graham Scan)
Hashing
Sorting
- Merge Sort
- Quick Sort
- Heap Sort
- Bubble Sort
- Insertion Sort
- Selection Sort
- Bucket Sort
- Count Sort
- Radix Sort
- Pancake Sort