{{ message }}

Instantly share code, notes, and snippets.

# sharmaeklavya2/cp_syllabus.md

Last active Jul 2, 2022
Competitive Programming Syllabus

# 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

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