Skip to content

Latest commit

 

History

History
612 lines (581 loc) · 49.1 KB

CodeChef-CCDSAP-Prepare.md

File metadata and controls

612 lines (581 loc) · 49.1 KB

CodeChef-CCDSAP-Prepare

This section lists out the syllabus, the learning resources and Mock Tests to help you prepare for the Certification test. The resources that we list here are references that we have collected over the internet and some of them from our own website. While we do recommend these resources based on the inputs of our user community, we do not claim that these are the most authoritative Learning Resources about any topic. Please feel free to find out what suits best to you.

We have also prepared a Mock Test for each level. A Mock Test is an open assessment contest that will help you assess yourself for the certification exam after you are ready with the topics. For each level we have different Mock Tests. These contests will run forever. We strongly recommend you to solve these problems in the same duration of time as the duration of the exam before you take the exam.

Candidates can expect problems from the following topics to come in the exam.

Foundation Level

Syllabus:

The syllabus for each level is mentioned below:

  • Basic Data Structures: Arrays, Strings, Stacks, Queues
  • Asymptotic analysis (Big-O notation)
  • Basic math operations (addition, subtraction, multiplication, division, exponentiation)
  • Sqrt(n) primality testing
  • Euclid’s GCD Algorithm
  • Basic Recursion
  • Greedy Algorithms
  • Basic Dynamic Programming
  • Naive string searching
  • O(n logn) Sorting
  • Binary Searching

Learning Resources:

Mock Test:

Advanced Level

This level is intended to test that the candidate has a very good grasp of algorithms and data structures, and can solve most problems that arise in practice. Candidates can expect problems from the following topics to come in the exam.

Syllabus:

Everything in the 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

Learning Resources:

Mock Test:

Expert Level

This level is intended to test that the candidate is an expert in algorithms and data structures, and has a deep understanding of the topics. Candidates can expect problems from the following topics to come in the exam.

Syllabus:

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 (eg. Convex Hull Trick, Divide and Conquer Optimization, Knuth Optimization)
  • Advanced String algorithms (Tries, KMP, Aho-Corasik, Suffix arrays, Suffix trees)
  • Flows (Max-Flow, Min Cost Max Flow)
**Note**: This is not an exhaustive list of the topics covered under Expert. As mentioned, the syllabus is open-ended.

Learning Resources:

  • The resources are listed here.

Mock Test:

Content taken from CodeChef.