Programming Contest Detailed Syllabus Along with Example Problems

general
,
1

Competitive Programming Syllabus

Note that in general, the syllabus for Competitive Programming is open-ended. For ACM ICPC, the syllabus is not mentioned anywhere, whereas IOI syllabus is specified before the start of the contest each year. The below syllabus is kind of detailed topics from which you may face questions in competitive programming related competitions.

Geometry

String Algorithms

Substring search

Suffix Arrays

  • O(n^2 * logn) Naive method of suffix array construction
  • O(n * logn^2) method of suffix array construction
  • O(n * logn) method of suffix array construction
  • O(n) method of suffix array construction
  • O(n) LCA preprocess on Suffix Arrays to solve a variety of string problems

Suffix Trees

  • O(n) construction of Suffix trees using Ukkonon’s algorithm
  • O(n) construction of Suffix Trees if provided with Suffix Arrays using Farach’s algorithm

Other

  • Suffix Automata - O(n) Suffix Automaton construction.
  • Dictionary Of Basic Factors - O(n * logn) method of DBF construction using Radix Sort.
  • Manacher’s algorithm to find length of palindromic substring of a string centered at a position for each position in the string.
    Runtime -> O(n).
  • Searching and preprocessing Regular Expressions consisting of ‘?’ and ‘*’

Multi-dimensional pattern matching

Graphs

Basic Graphs

  • Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios
  • Breadth First Search (Problems - PPATH, ONEZERO, WATER on SPOJ)
  • Depth First Search
  • Strongly Connected Components (TOUR and BOTTOM on SPOJ)
  • Biconnected Components, Finding articulation points and bridges (RELINETS, PT07A on SPOJ)
  • Dijkstra algorithm (SHPATH on SPOJ)
  • Floyd Warshall algorithm (COURIER on SPOJ)
  • Minimum Spanning Tree (BLINNET on SPOJ)
  • Flood-fill algorithm
  • Topological sort
  • Bellman-Ford algorithm.
  • Euler Tour/Path (WORDS1 on SPOJ)
  • Suggested reading for most of the topics in Graph algorithms -
    http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1.
  • Also refer to the tutorial for problems concerning these techniques.
  • Cormen chapter 22 to 24.

Flow networks/ matching

Dynamic Programming.

Greedy

Number Theory

Modulus arithmetic

Fermat’s theorem, Euler Totient theorem (totient function, order, primitive roots)

Chinese remainder theorem

Primality tests

GCD using euclidean method

Logarithmic Exponentiation

Integer Factorization

Other

Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)

Probability

Counting

Special numbers

Advanced counting techniques - Polya counting, burnsides lemma

Game theory

Linear Algebra

Matrix Operations

Matrix transformations (Transpose, Rotation of Matrix, Representing Linear transformations using matrix)

Solving system of linear equations

Using matrix exponentiation to solve recurrences

Eigen values and Eigen vectors

Polynomials

Permutation cycles

  • Suggested Reading - Art of Computer Programming by Knuth Vol. 3
  • Problems - ShuffleMethod, Permutation and WordGame on topcoder.

Group Theory (Advanced Techniques)

Generating functions

  • Suggested Reading
    • Herbert Wilf’s generating functionology
    • Robert Sedgewick and Flajoulet’s Combinatorial analysis

Data Structures

Basic

Singly/Doubly Linked List

Hash Tables

Circular linked list / queue

Binary/n-ary trees

Heaps

Trie

Interval trees / Segment Trees

Fenwick (Binary Indexed) trees

Disjoint data structures

Range minimum Query (RMQ)

Customized interval/segment trees (Augmented DS)

AVL Trees

Miscellaneous

  • Splay Trees
  • B/B+ Trees
  • k-d Trees
  • Red-black Trees
  • Skip List
  • Binomial/ Fibonacci heaps

Exercices

Persistent Segment Tree

Centroid Decomposition

Heavy Light Decomposition

Search Techniques/Bruteforce writing techniques/Randomized algorithms.

Backtracking (beginner)

  • N queens problems
  • Knights Tour
  • Sudoku Problem
  • Tiling Problem
  • 15 puzzle.

Dancing Links and Algorithm X given by Knuth (advanced)

Binary Search (beginner)

Ternary Search (intermediate)

Meet in the middle (Intermediate)

Hill Climbing (Advanced)

Simulated Annealing (Advanced)

Regular Iteration to reach a fixed point (Advanced)

  • Newton-Raphson method to find root of a mathematical function.
  • Iterations to solve linear non homogeneous system of equations.

Representing sets with bitmasks and manipulating bitmasks (Beginner)

General programming issues in contests

References:

31 Likes
2

There is no such thing as “Syllabus for competitive programming”. Though, the list is quite exhaustive and helpful but the title is of course ridiculous.

2 Likes
3

Added a comment, in the beginning, to clarify this up.

8 Likes
4

Thanks admin!!

5

Very Nice and Helpful.Thanks to the team for the effort.

6

reference drive link not working.

1 Like
7

what should be the order in doing this course

8

The syllabus is majorly taken from here:

Was that prepared by Codechef? If not, then I think credits should be given rather than posting falsely here as it is.

2 Likes
9

Why do you think it was falsely posted? The link to the original doc was given in the References section.

2 Likes
10

Fixed now.

11

I thought that because at the time I posted that comment, the link was not working. Thanks for the fix :slight_smile:

12

Very helpful