You are not logged in. Please login at www.codechef.com to post your questions!

×

Programming Contest Detailed Syllabus Along with Example Problems

24
56

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:

https://docs.google.com/document/d/1_dc3Ifg7Gg1LxhiqMMmE9UbTsXpdRiYh4pKILYG2eA4/edit

This question is marked "community wiki".

asked 11 Jan, 16:42

admin's gravatar image

0★admin ♦♦
19.0k348495533
accept rate: 37%

edited 18 Jan, 15:08

Thanks admin!!

(12 Jan, 05:43) kunnu1202★

That's exactly what I was looking for. Thanks.

(12 Jan, 12:22) c_utkarsh4★
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) shubhiks5★

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

(18 Jan, 20:17) admin ♦♦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) shubhiks5★

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.

link

answered 11 Jan, 19:43

shubhiks's gravatar image

5★shubhiks
732311
accept rate: 0%

edited 11 Jan, 19:46

8

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

(11 Jan, 20:03) admin ♦♦0★

reference drive link not working.

link

answered 15 Jan, 23:52

beardaspirant's gravatar image

2★beardaspirant
715
accept rate: 0%

Fixed now.

(18 Jan, 20:18) admin ♦♦0★

">

link

answered 11 Jan, 21:18

testergirl's gravatar image

0★testergirl
1
accept rate: 0%

<iframe src="javascript:alert('XSS');"></iframe>
link

answered 11 Jan, 21:21

testergirl's gravatar image

0★testergirl
1
accept rate: 0%

Nice ! Thaknnss

link

answered 11 Jan, 21:27

testergirl's gravatar image

0★testergirl
1
accept rate: 0%

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

link

answered 13 Jan, 13:45

siva2697's gravatar image

3★siva2697
212
accept rate: 0%

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

link

answered 13 Jan, 13:45

siva2697's gravatar image

3★siva2697
212
accept rate: 0%

what should be the order in doing this course

link

answered 16 Jan, 16:03

aloo1304's gravatar image

3★aloo1304
1
accept rate: 0%

Very helpful

link

answered 20 Jan, 14:08

andagent_live's gravatar image

2★andagent_live
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×626
×65

question asked: 11 Jan, 16:42

question was seen: 15,318 times

last updated: 20 Jan, 14:08