Graph Topics
| Graphs (GR) | |||||
|---|---|---|---|---|---|
| Basic Structure and Algorithms | |||||
| Graph Representation | CP 2.4.1 | CLRS 22.1 | |||
| Graph Traversal (DFS/BFS) | CP 4.2.1-2 | CLRS 22.2, 22.3 | Maximal 1 | Maximal 2 | |
| Flood Fill - Connected Components (Undirected Graphs) | CP 4.2.3-4 | Maximal | |||
| Toplogical Sort (DAG) | CP 4.2.5 | Wikipedia | CLRS 22.4 | Maximal | |
| Bipartite Graph Check | CP 4.2.6 | ||||
| Graph Edge Types | CP 4.2.7 | CLRS 22.3 | |||
| Aritculation Points and Bridges (Undirected Graphs) | CP 4.2.8 | Maximal 1 | Maximal 2 | Maximal 3 | CF Blog |
| Biconnected Component and Block-cut Tree | Wikipedia | Library | |||
| Bridge Tree | Quora | Library | |||
| Strongly Connected Components (Directed Graphs) | CP 4.2.9 | CLRS 22.5 | Maximal | ||
| Minimum Spanning Tree (MST) | |||||
| Kruskal's Algorithm | CP 4.3.2 | CLRS 23 | |||
| Prim's Algorithm | CP 4.3.3 | CLRS 23 | |||
| MST Variants | CP 4.3.4 | ||||
| Shortest Path Problem | |||||
| SSSP on Unweighted Graph (BFS) | CP 4.4.2 | ||||
| SSSP on Unweighted Graph (Dijkstra's Algorithm) | CP 4.4.3 | Maximal 1 | Maximal 2 | ||
| SSSP on Weighted Graph with Negative Cycles (Bellman-Ford's Algorithm) | CP 4.4.4 | ||||
| APSP (Floyd Warshall's Algorithm) | CP 4.4.5 | ||||
| Network Flow | |||||
| Ford Fulkerson's Method | CP 4.6.2 | ||||
| Edmonds Karp's Algorithm | CP 4.6.3 | ||||
| Max Flow: Graph Modeling | CP 4.6.4 | CP 4.6.6 | |||
| Max Flow: Applications and Variants | CP 4.6.5 | Topcoder 1 | Topcoder 2 | ||
| Minimum Cost (Max) Flow | CP 9.23 | Topcoder | |||
| Directed Acyclic Graph (DAG) | |||||
| Shortest/Longest Path | CP 4.7.1 | ||||
| Counting Paths | CP 4.7.1 | ||||
| Converting General Graph to DAG | CP 4.7.1 | ||||
| Minimum Path Cover (MPC) | CP 9.24 | ||||
| Trees | |||||
| Basic Properties | CP 4.7.2 | CF Blog | |||
| Minimum Vertex Cover (MVC) - DP on Trees | CP 4.7.1 | ||||
| Max Weighted Independent Set (MWIS) - DP on Trees | CP 9.22 | ||||
| Lowest Common Ancestor | CP 9.18 | Topcoder | CF Blog | CF Blog | |
| DSU on Trees | CF blog | ||||
| Centroid Decomposition | Quora | Blog | |||
| Bipartite Graph | |||||
| Maximum Cardinality Bipartite Matching (MCBM) | CP 4.7.4 | ||||
| Maximum Independet Set (MIS) and MVC | CP 4.7.4 | ||||
| Max Weighted Independent Set (MWIS) | CP 9.22 | ||||
| Hungarian Algorithm | Maximal | Topcoder | |||
| Special Graphs | |||||
| Eulerian Graph | CP 4.7.3 | CF Blog |
Maths Topics
| Mathematics (MT) | |||||
|---|---|---|---|---|---|
| Combinatorics | |||||
| Fibonacci Numbers | Maximal | CP 5.4.1 | Wiki - Fibonacci Number | Wiki - Pisano Period | |
| Binomial Coefficient | CP 5.4.2 | Maximal | Wiki - Binomial Theorem | Wiki - Binomial Coefficient | Wiki - Stars and Bars |
| Catalan Numbers | Wikipedia | Maximal | CP 5.4.3 | ||
| Inclusion-Exclusion Principle | Maximal | ||||
| Pigeonhole Principle | Cut The Knot | ACP | Quora | Wikipedia | |
| Burnside's Lemma | IMO Math | Brilliant | Maximal | Whitman | |
| Number Theory | |||||
| Prime Numbers | CP 5.5.1 | Maximal 1 | Maximal 2 | ACP | Topcoder |
| Perfect Numbers | Wikipedia | ||||
| Euclidean Algorithm (GCD and LCM) | CP 5.5.2 | Maximal | |||
| Prime Factorization | CP 5.5.4 | CP 5.5.5 | ACP | ||
| Factorial | CP 5.5.3 | ACP | |||
| Functions Involving Prime Factors | CP 5.5.6 | ||||
| Euler's Totient (Phi) Function | Maximal | CP 5.5.6 | |||
| Modified Sieve | CP 5.5.7 | ||||
| Modular Arithmetic | CP 5.5.8 | Khan | Maximal | ACP | |
| Extended Euclidean Algorithm | CP 5.5.9 | Maximal | Wikipedia | ||
| Modular Equation (AX = B) | Maximal | ||||
| Diophantine Equation (AX + BY = C) | Maximal | ||||
| Discrete Logarithm | Maximal | ||||
| Moebius Function | ACP | ||||
| Probability Theory | |||||
| Basics of Probability Theory | Math 4 lectures (3 to 7) | CP 5.6 | ACP (7 videos) | Topcoder | |
| Probabilistic Analysis | CLRS 5 | ||||
| Gambler's Ruin Problem | Wikipedia | ||||
| Cycle Finding | |||||
| Game Theory | |||||
| Decision Tree and Minimax Strategy | CP 5.8 | ||||
| Nim Game and Sprague-Grundy Theorem | Maximal | Topcoder | Blog 1 | Blog 2 | |
| Games on General Graphs | Maximal | Library 1 | Library 2 | ||
| Numerical Methods | |||||
| Newton's Method | Wikipedia | Maximal | Notes | ||
| Ruffini–Horner's method | Wikipedia | Notes | |||
| Others | |||||
| Ad Hoc/Elementary Math | CP 5.2 | ACP | |||
| Canonical Form | Wikipedia | ||||
| Binary Exponentiation | Maximal | ||||
| BigInteger (Long Arithmetic) | CP 5.3 | ||||
| Factorial Number System | Wikipedia | ||||
| Matrix Multiplication | CP 9.20 | ||||
| Matrix Power | CP 9.21 | ||||
| Specific Problems and Algorithms | |||||
| Specific Problems | |||||
| Magic Square | CP 9.19 | ||||
| Pancake Sorting | CP 9.25 | ||||
| Roman Numerals | CP 9.28 | ||||
| Selection Problem | CP 9.29 | ||||
| Tower of Hanoi | CP 9.34 | ||||
| Range Minimum Query | Maximal | ||||
| Specific Algorithms | |||||
| Partially Ordered Sets | CF Blog |
Data Structures
| Data Structures (DS) | ||||||
|---|---|---|---|---|---|---|
| Sortings | ||||||
| 1 | Merge Sort | CLRS 2.3 | ||||
| 2 | Inversion Index | CP 9.14 | ||||
| 3 | Counting Sort | CP 9.32 | Wikipedia | CLRS 8.2 | ||
| 4 | Radix Sort | CP 9.32 | CLRS 8.3 | |||
| Linear Data Structures | ||||||
| 5 | Basic data structures | CP 2.2 | CLRS 10 | |||
| 6 | BitSet and Bitmasks | CP 2.2 | ||||
| 7 | Modified Stacks/Queues for finding minimum in O(1) | Maximal | ||||
| Non-Linear Data Structures | ||||||
| 8 | Treemaps and Treesets | CP 2.3 | ||||
| 9 | Hashmaps and Hashsets | CP 2.3 | Effective Java (item 9) | CLRS 11 | ||
| Tree-Related Data Structures | ||||||
| 10 | Segment Tree | CP 2.4.3 | Maximal | |||
| 11 | Fenwick Tree (BIT) | CP 2.4.4 | TC tutorials | Blog | Maximal | Kth Element |
| 12 | Heap (and Priority Queue) | GeeksForGeeks | CLRS 6 | Tutorial | CP 2.3 | |
| 13 | Treaps | Quora | Maximal | Library | ||
| 14 | Randomized Heap | Maximal | ||||
| 15 | Binary Search Tree | CLRS 12 | ||||
| 16 | Fibonacci Heap | CLRS 19 | ||||
| Other Data Structures | ||||||
| 17 | Disjoint-Sets Union (DSU) | CP 2.4.2 | Maximal | CLRS 21 | CF Blog | |
| 18 | Sparse Table | CP 9.33 | Blog | |||
| 19 | SQRT Decomposition | Maximal | ||||
| 20 | Treaps (Randomized Cartesian Tree) | Maximal | Quora | Habrahabr | Comparison |