4
Competitive Programming Syllabus
source link: https://gist.github.com/sharmaeklavya2/8aa2830f3a46a3f46ff249b4e1f07767
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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)
- Suggested Reading - http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
- Rotating Calipers Technique
- Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html
- Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.
- Line Sweep/Plane Sweep algorithms
- Area/Perimeter of Union of Rectangles.
- Closest pair of points.
- Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep
- Problems - Follow the tutorial for list of problems.
- 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
- KnuthMorrisPratt algorithm (Problems - NHAY, PERIOD on SPOJ)
- Suggested Reading - Cormen chapter on Strings.
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
- Aho Corasick algorithm
- Problems - WPUZZLES on SPOJ
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
- 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
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
- 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)
- problems - GREED, SCITIES, TOURS on SPOJ | http://www.topcoder.com/stat?c=problem_statement&pm=8143
- 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.
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
Greedy
- Chapter on Greedy algorithms in Cormen
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg
- Problems - refer to the topcoder tutorial.
Number Theory
Modulus arithmetic
Fermat's theorem, Euler Totient theorem (totient function, order, primitive roots)
Chinese remainder theorem
- Suggested Reading
- 31.5 from Cormen
- 1.6 from Number Theory by SY Yan
- Problems
- Project Euler 271
- http://www.topcoder.com/stat?c=problem_statement&pm=10551&rd=13903
Primality tests
- Deterministic O(sqrt(n)) approach
- Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test
- Suggested Reading -
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
- Cormen 31.8
- 2.2 from Number Theory by SY Yan
- Problems
- PON, PRIC, SOLSTRAS on SPOJ
- http://www.topcoder.com/stat?c=problem_statement&pm=4515
- Prime generation techniques - Sieve of Erastothenes (PRIME1 on SPOJ)
GCD using euclidean method
- Suggested Reading - 31.2 Cormen
- Problems
Logarithmic Exponentiation
- Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
Integer Factorization
Other
- Stirling numbers
- Wilson theorem
- nCr % p in O(p) preprocess and O(log n) query
- Lucas Theorem
- Suggested Reading for Number Theory -
- Number theory for computing by Song Y Yan (Simple book describing concepts in details)
- Concepts are also superficially covered in Chapter 31 of Introduction to Algorithms by Cormen
- http://www.codechef.com/wiki/tutorial-number-theory
- http://www.algorithmist.com/index.php/Category:Number_Theory
Problems on Number Theory -
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
- 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)
Solving system of linear equations
- Suggested Reading
- 28.3 Cormen
- Linear Algebra by Kenneth Chapter 1
- Problems
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
- Problems - https://www.spoj.pl/problems/POSTERS/
- Reading: CLRS: section 10.2, Mark Allen Weies Chapter 3
Hash Tables
Circular linked list / queue
- Problems - https://www.spoj.pl/problems/CTRICK/
Binary/n-ary trees
- Reading
- CLRS: section 10.4
- CLRS: Chapter 12
- Mark Allen Weies Chapter 4
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack
Heaps
Interval trees / Segment Trees
Fenwick (Binary Indexed) trees
Disjoint data structures
Range minimum Query (RMQ)
Customized interval/segment trees (Augmented DS)
AVL Trees
- Problem - https://www.spoj.pl/problems/ORDERS/
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)
- problems - PRLGAME, SUDOKU, NQUEEN on SPOJ
- Suggested reading - http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
Binary Search (beginner)
- problems - AGGRCOW on SPOJ. Refer the tutorial for more problems.
- finding all real roots of a polynomial using binary search (intermediate)
- Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch
Ternary Search (intermediate)
Meet in the middle (Intermediate)
- problems - http://www.spoj.pl/problems/MAXISET/
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)
- Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation
- problems - refer to the tutorial link in Suggested reading section.
General programming issues in contests
- Arithmetic Precision (Beginner)
- Suggested Reading - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK