×

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.

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.

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

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.

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:

This question is marked "community wiki".

19.5k348496535
accept rate: 36%

(12 Jan, 05:43) 1★
2

The syllabus is majorly taken from here: https://docs.google.com/document/d/1_dc3Ifg7Gg1LxhiqMMmE9UbTsXpdRiYh4pKILYG2eA4/edit

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

(16 Jan, 17:52) 4★
2

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

(18 Jan, 20:17) 0★

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

(19 Jan, 00:26) 4★

 1 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. answered 11 Jan, 19:43 4★shubhiks 732●3●11 accept rate: 0% 8 Added a comment, in the beginning, to clarify this up. (11 Jan, 20:03) admin ♦♦0★
 1 reference drive link not working. answered 15 Jan, 23:52 71●5 accept rate: 0% Fixed now. (18 Jan, 20:18) admin ♦♦0★
 0 Very Nice and Helpful.Thanks to the team for the effort. answered 13 Jan, 13:45 4★siva2697 21●3 accept rate: 0%
 0 what should be the order in doing this course answered 16 Jan, 16:03 2★aloo1304 21●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×733
×65