 # Syllabus of Certification

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

• 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)
//