# 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

• Graham Scan algorithm for Convex Hull O(n * log(n))
• Monotone Chain algorithm for Convex Hull O(n * log(n)) (This is easier to implement than Graham Scan)
• Online construction of 3-D convex hull in O(n^2)
• Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn)
• Rotating Calipers Technique
• Line Sweep/Plane Sweep algorithms
• Area/Perimeter of Union of Rectangles.
• Closest pair of points.
• Area of Union of Circles.
• Delaunay Triangulation of n points in O(n * logn).
• Voronoi Diagrams of n points in O(n * logn) using Fortuneâs algorithm.
• Point in a polygon problem -
• O(n) solution without preprocessing.
• O(logn) algorithm with O(n * logn) preprocessing for convex polygons.
++ Sample Implementations of these routines can be seen here: https://gist.github.com/msg555/7207431
• Problems on computational geometry -
• BSHEEP, BULK, SEGVIS, CONDUIT, RUNAWAY, DIRVS, RAIN1, SHAMAN, TCUTTER, LITEPIPE, RHOMBS, FSHEEP,
FLBRKLIN, CERC07P, BAC, ALTARS, CERC07C, NECKLACE, CH3D, RECTANGL, POLYSSQ, FOREST2, KPPOLY,
RAIN2, SEGMENTS, ARCHPLG, BALLOON, CIRCLES, COMPASS, EOWAMRT, ICERINK on SPOJ.
• CultureGrowth, PolygonCover on Topcoder.
• Suggested Reading - Computational Geometry: Algorithms and applications. Mark De Burg.

## String Algorithms

### 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 â*â

## 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.

## Dynamic Programming.

• Suggested Reading - Dynamic Programming(DP) as a tabulation method
• Cormen chapter on DP
• Standard problems (you should really feel comfortable with these types)
• State space reduction
• Solving in the reverse - easier characterizations looking from the end
• Counting/optimizing arrangements satisfying some specified properties
• Strategies and expected values
• DP on probability spaces
• DP on trees
• Symmetric characterization of DP state
• A good collection of problems

## Number Theory

### Fermatâs theorem, Euler Totient theorem (totient function, order, primitive roots)

• 1.6, 2.2 from Number Theory by SY Yan
• 31.6 , 31.7 from Cormen
• Problems

### GCD using euclidean method

• Suggested Reading - 31.2 Cormen
• Problems

### Integer Factorization

• Naive O(sqrt(n)) method
• Pollard Rho factorization
• 2.3 from Number Theory SY Yan
• 31.9 Cormen
• Problems -

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

### Counting

• Basic principles - Pigeon hole principle, addition, multiplication rules
• Problems
• Inclusion-exclusion

## Game theory

• Basic principles and Nim game
• Sprague grundy theorem, grundy numbers
• Suggested problems
• Hackenbush
• Suggested problems

## Linear Algebra

### Matrix Operations

• Addition and subtraction of matrices
• Cormen 28.1
• Multiplication (Strassenâs algorithm), logarithmic exponentiation
• Cormen 28.2
• Linear Algebra by Kenneth Hoffman Section 1.6
• Problems

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

• Suggested Reading - Linear Algebra By Kenneth Hoffman Section 3.1,3.2,3.4,3.7
• Problems
• Determinant, Rank and Inverse of Matrix (Gaussean Elimination , Gauss Jordan Elimination)
• 28.4 Cormen
• Linear Algebra by Kenneth Chapter 1
• Problems

### Solving system of linear equations

• 28.3 Cormen
• Linear Algebra by Kenneth Chapter 1
• Problems

• Problems

## Permutation cycles

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

## Generating functions

• Herbert Wilfâs generating functionology
• Robert Sedgewick and Flajouletâs Combinatorial analysis

## Data Structures

### Hash Tables

• Problems
• Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5

### Heaps

• Problems
• Reading : Mark Allen Weies Chapter 6

### Customized interval/segment trees (Augmented DS)

• Problems
• Reading: CLRS: Chapter 14 (augmented DS)

### Miscellaneous

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

## Search Techniques/Bruteforce writing techniques/Randomized algorithms.

### Backtracking (beginner)

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

### Binary Search (beginner)

• problems - AGGRCOW on SPOJ. Refer the tutorial for more problems.
• finding all real roots of a polynomial using binary search (intermediate)

### Meet in the middle (Intermediate)

• This is used for optimization problems where finding optimal solution is hard.

### 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.

## General programming issues in contests

### References:

74 Likes

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.

3 Likes

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

1 Like

what should be the order in doing this course

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

8 Likes

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

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

2 Likes

Fixed now.

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

Aho Corasick pdf link is broken (under strings section).

Awesome Content for ICPC preparation