Skip to content

Instantly share code, notes, and snippets.

@idiotleon

idiotleon/cp_syllabus.md

Forked from sharmaeklavya2/cp_syllabus.md
Created May 10, 2020 05:49
Show Gist options
  • Save idiotleon/be34bec1b56dcf8f1a96e3328da2d1e3 to your computer and use it in GitHub Desktop.
Save idiotleon/be34bec1b56dcf8f1a96e3328da2d1e3 to your computer and use it in GitHub Desktop.
Download ZIP
Competitive Programming Syllabus
Raw
cp_syllabus.md

Competitive Programming Syllabus

Geometry

  • Graham Scan algorithm for Convex Hull O(n * log(n))
  • 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.
  • 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

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

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

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)

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment