Foundation: 2 cakewalk, 2 simple and 1 easy (100 * 2 + 150 * 2 + 1 * 200 = 700)
Advanced: 1 cakewalk, 1 simple, 2 easy, 1 easy medium (100 + 150 + 2 * 200 + 250 = 900)
Foundation Level
- Asymptotic analysis (Big-O notation)
- Basic Data Structures, e.g. Arrays, Strings, Stacks, Queues
- Basic math operations (addition, subtraction, multiplication, division, exponentiation)
- Euclid’s GCD Algorithm
- Sqrt(n) primality testing, finding divisors in \mathcal{O}(\sqrt(N)) time.
- Basic Recursion
- Greedy Algorithms
- Basic Dynamic Programming
- Naive string searching
- \mathcal{O}(N \log{N}) Sorting
- Binary Search
Advanced Level
- Everything in Foundation Level, along with:
- Heaps (priority queue)
- Disjoint Set Union
- Segment Trees
- Binary Index Tree (Fenwick tree)
- Trees (traversals, tree dynamic programming)
- Finding Lowest Common Ancestors (O(log N) solution where N is number of nodes).
- Graph Algorithms:
- Finding connected components and transitive closures.
- Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
- Minimum spanning tree (Prim and Kruskal algorithms)
- Biconnectivity in undirected graphs (bridges, articulation points)
- Strongly connected components in directed graphs
- Topological Sorting
- Euler path, tour/cycle.
- Modular arithmetic including division, inverse
- Amortized Analysis
- Divide and Conquer
- Advanced Dynamic Programming problems (excluding the dp optimizations which are added in expert level)
- Sieve of Eratosthenes
Expert Level
- The syllabus for Expert Level is open-ended. Everything in Advanced Level will be included, along with:
- Treaps
- Persistent Data Structures
- HLD
- Centroid Decomposition
- Computational Geometry
- Fast Fourier Transforms
- Game Theory
- Gaussian Elimination
- Dynamic Programming Optimizations
- Advanced String algorithms (Tries, KMP, Aho-Corasik, Suffix arrays, Suffix trees)
- Flows (Max-Flow, Min Cost Max Flow)