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

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)