View Code? Open in Web Editor
NEW
This project forked from ashutoshjv661 /maths-cp-syllabus
Maths for competitive Programming
maths-cp-syllabus's Introduction
A comprehensive list of Mathematics Topics for Competitive Coding. This list is not orginally written by me but will always help you in your journey of Competitive Programming ^_^ 🥳🔥 Competitive Programming Syllabus
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.
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
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
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
DISUBSTR, PLD, MSTRING, REPEATS, JEWELS, ARCHIVER, PROPKEY, LITELANG, EMOTICON, WORDS, AMCODES, UCODES, PT07H, MINSEQ, TOPALIN, BWHEELER, BEADS, SARRAY, LCS, LCS2, SUBST1, PHRASES, PRETILE on SPOJ
http://www.algorithmist.com/index.php/Category:String_algorithms
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.
Maximum flow using Ford Fulkerson Method
Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
problems - TAXI, POTHOLE, IM, QUEST4, MUDDY, EN, CABLETV, STEAD, NETADMIN, COCONUTS, OPTM on SPOJ.
Maximum flow using Dinic’s Algorithm (PROFIT on spoj)
Minimum Cost Maximum Flow.
Successive Shortest path algorithm.
Cycle Cancelling algorithm - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1
Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/ Hungarian Method)
Stoer Wagner min-cut algorithm.
Hopcroft Karp bipartite matching algorithm (ANGELS on SPOJ)
Maximum matching in general graph (blossom shrinking)
Gomory-Hu Trees (MCQUERY on Spoj)
Chinese Postman Problem
Suggested Reading for the full category ->
Network flow - Algorithms and Applications by Ahuja
Cormen book chapter 25.
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
Basic postulates (Including modular linear equations, Continued fraction and Pell's equation)
Suggested Reading -
Problems
Fermat's theorem, Euler Totient theorem (totient function, order, primitive roots)
Suggested Reading
1.6, 2.2 from Number Theory by SY Yan
31.6 , 31.7 from Cormen
Problems
Chinese remainder theorem
Suggested Reading
31.5 from Cormen
1.6 from Number Theory by SY Yan
Problems
Deterministic O(sqrt(n)) approach
Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test
Suggested Reading -
Problems
Prime generation techniques - Sieve of Erastothenes (PRIME1 on SPOJ)
GCD using euclidean method
Suggested Reading - 31.2 Cormen
Problems
Logarithmic Exponentiation
Naive O(sqrt(n)) method
Pollard Rho factorization
Suggested Reading
2.3 from Number Theory SY Yan
31.9 Cormen
Problems -
Stirling numbers
Wilson theorem
nCr % p in O(p) preprocess and O(log n) query
Lucas Theorem
Suggested Reading for Number Theory -
Problems on Number Theory -
Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)
Basic probability and Conditional probability
Random variables, probability generating functions
Mathematical expectation + Linearity of expectation
Special discrete and continuous probability distributions
Suggested Readings
Basic principles - Pigeon hole principle, addition, multiplication rules
Problems
Suggested readings
Inclusion-exclusion
Advanced counting techniques - Polya counting, burnsides lemma
Suggested reading
Problems
Basic principles and Nim game
Sprague grundy theorem, grundy numbers
Suggested readings
Suggested problems
Hackenbush
Suggested problems
Addition and subtraction of matrices
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
Suggested Reading
28.3 Cormen
Linear Algebra by Kenneth Chapter 1
Problems
Using matrix exponentiation to solve recurrences
Suggested Reading
Problems
Eigen values and Eigen vectors
Roots of a polynomial (Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial)
Lagrange Interpolation
Suggested Reading - Art of Computer Programming by Knuth Vol. 3
Problems - ShuffleMethod, Permutation and WordGame on topcoder.
Burnside Lemma
Polya’s theorem
Suggested Reading
Problems
Suggested Reading
Herbert Wilf's generating functionology
Robert Sedgewick and Flajoulet's Combinatorial analysis
Arrays/Stacks/Queues
Problems
Reading:
Singly/Doubly Linked List
Problems
Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5
Circular linked list / queue
Problems
Reading : Mark Allen Weies Chapter 6
Interval trees / Segment Trees Fenwick (Binary Indexed) trees Range minimum Query (RMQ) Customized interval/segment trees (Augmented DS)
Problems
Reading: CLRS: Chapter 14 (augmented DS)
Splay Trees
B/B+ Trees
k-d Trees
Red-black Trees
Skip List
Binomial/ Fibonacci heaps
Search Techniques/Bruteforce writing techniques/Randomized algorithms.
N queens problems
Knights Tour
Sudoku Problem
Tiling Problem
15 puzzle.
Dancing Links and Algorithm X given by Knuth (advanced) Ternary Search (intermediate) Meet in the middle (Intermediate) 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
maths-cp-syllabus's People
Contributors
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent