- 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 - Algorithmic Geometry
- Rotating Calipers Technique.
- Suggested Reading - Rotating Calipers
- 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 - Line Sweep
- 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
- Knuth-Morris-Pratt algorithm.
- Aho-Corasick algorithm.
- 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.
- Suffix Automata
- O(n) Suffix Automaton construction.
- Dictionary Of Basic Factors
- O(n * log n) 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 ‘?’, ‘*’.
- Multi-dimensional pattern matching.
- Problems on Strings
- 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.
- Problems - TOUR and BOTTOM on SPOJ.
- Biconnected Components, Finding articulation points and bridges.
- Problems - RELINETS, PT07A on SPOJ.
- Dijkstra algorithm.
- Problems - SHPATH on SPOJ.
- Floyd Warshall algorithm.
- Problems - COURIER on SPOJ.
- Minimum Spanning Tree.
- Problems - BLINNET on SPOJ.
- Flood-fill algorithm.
- Topological sort.
- Bellman-Ford algorithm.
- Euler Tour/Path.
- Problems - WORDS1 on SPOJ.
- Suggested reading for most of the topics in Graph algorithms
- Graph Algorithms Tutorial.
- Also refer to the tutorial for problems concerning these techniques.
- Cormen chapter 22 to 24.
- Maximum flow using Ford Fulkerson Method.
- Suggested Reading - Max Flow
- Problems - TAXI, POTHOLE, IM, QUEST4, MUDDY, EN, CABLETV, STEAD, NETADMIN, COCONUTS, OPTM on SPOJ.
- Maximum flow using Dinic’s Algorithm.
- Problems - PROFIT on SPOJ.
- Minimum Cost Maximum Flow.
- Successive Shortest path algorithm.
- Cycle Cancelling algorithm.
- Suggested Reading - Min Cost Flow
- Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/Hungarian Method).
- Problems - GREED, SCITIES, TOURS on SPOJ & This TopCoder Problem
- Stoer Wagner min-cut algorithm.
- Hopcroft Karp bipartite matching algorithm.
- Problems - ANGELS on SPOJ.
- Maximum matching in general graph (blossom shrinking).
- Gomory-Hu Trees.
- Problems - MCQUERY on Spoj.
- Chinese Postman Problem.
- Problems - Chinese Postman Problem
- Suggested Reading - Chinese Postman
- 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 feel really comfortable with these two).
- State space reduction.
- Solving in reverse - easier characterizations looking from the end.
- Counting/optimizing arrangements satisfying some specified properties.
- http://www.topcoder.com/stat?c=problem_statement&pm=8306
- http://www.topcoder.com/stat?c=problem_statement&pm=784
- 9 Strategies and expected values
- http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183
- http://www.topcoder.com/stat?c=problem_statement&pm=10806
- http://www.topcoder.com/stat?c=problem_statement&pm=7828
- http://www.topcoder.com/stat?c=problem_statement&pm=7316
- DP on probability spaces.
- DP on trees.
- DP with data structures.
- Problems - INCSEQ, INCDSEQ, LIS2 on SPOJ.
- http://www.topcoder.com/stat?c=problem_statement&pm=1986
- Symmetric characterization of DP state.
- Problems - Symmetric DP Problem.
- A good collection of problems.
- Suggested Reading
- Chapter on Greedy algorithms in Cormen.
- Greedy Algorithm Tutorial.
- problems - refer to the topcoder tutorial.
- Modulus arithmetic - basic postulates (Including modular linear equations, Continued fraction and Pell's equation).
- Suggested Reading
- Chapter 1 from Number Theory for Computing by SY Yan [ Recommended ].
- 31.1, 31.3 and 31.4 from Cormen
- www.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers
- Problems
- Suggested Reading
- Fermat's theorem, Euler’s Totient theorem (totient function), Wilson's theorem, and Wilson's theorem related problems.
- Suggested Reading
- 1.6, 2.2 from Number Theory for Computing by SY Yan.
- 31.6, 31.7 from Cormen
- Problems
- Suggested Reading
- 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
- Suggested Reading
- 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
- Suggested Reading
- Prime generation techniques - Sieve of Eratosthenes
- Suggested Problems - PRIME1 on SPOJ
- GCD using euclidean method
- Suggested Reading
- 31.2 Cormen
- Problems -
- Suggested Reading
- Logarithmic Exponentiation
- Suggested Reading -
- Integer Factorization
- 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 -
- 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
-Basic probability and Conditional probability
- Suggested problems
- Random variables, probability generating functions
- Mathematical expectation + Linearity of expectation
- Special discrete and continuous probability distributions
- Bernoulli, Binomial, Poisson, normal distribution
- Suggested Problem
- Suggested Readings
- Cormen appendix C (very basic)
- Topcoder probabilty tutorial http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities
- http://en.wikipedia.org/wiki/Random_variable
- http://en.wikipedia.org/wiki/Expected_value
- William Feller, An introduction to probability theory and its applications
- Counting
- Basic principles - Pigeon hole principle, addition, multiplication rules
- Suggested problems
- Suggested readings
- Inclusion-exclusion
- Special numbers
- Suggested reading - Stirling, eulerian, harmonic, bernoulli, fibonacci numbers
- Suggested problems
- Advanced counting techniques - Polya counting, burnside lemma
- Basic principles - Pigeon hole principle, addition, multiplication rules
- Game theory
- Basic principles and Nim game
- Sprague grundy theorem, grundy numbers
- Suggested readings
- Suggested problems
- Hackenbush
- Basic principles and Nim game
- Linear Algebra
- Matrix Operations
- Addition and subtraction of matrices
- Suggested Reading
- Cormen 28.1
- Suggested Reading
- Multiplication ( Strassen's algorithm ), logarithmic exponentiation
- Suggested reading
- Cormen 28.2
- Linear Algebra by Kenneth Hoffman Section 1.6
- Problems
- Suggested reading
- 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
- Suggested Reading
- Determinant , Rank and Inverse of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
- Suggested Reading
- 28.4 Cormen
- Linear Algebra by Kenneth Chapter 1
- Problems
- Suggested Reading
- Solving system of linear equations
- Suggested Reading
- 28.3 Cormen
- Linear Algebra by Kenneth Chapter 1
- Problems -
- Suggested Reading
- Using matrix exponentiation to solve recurrences
- Suggested Reading
- Problems
- Eigenvalues and Eigen-vectors
- Addition and subtraction of matrices
- Polynomials
- Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]
- Problems
- http://www.topcoder.com/stat?c=problem_statement&pm=8273&rd=10798
- POLYEQ , ROOTCIPH on Spoj
- Problems
- Lagrange Interpolation
- Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]
- Matrix Operations
- Permutation cycles
- Suggested Reading
- Art of Computer Programming by Knuth Vol. 3
- Problems
- ShuffleMethod, Permutation and WordGame on topcoder.
- Suggested Reading
- Group Theory
- Burnside Lemma, Polya’s theorem
- Suggested Reading
- Hernstein's topics in algebra
- http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html
- Problems
- TRANSP on spoj
- http://www.topcoder.com/stat?c=problem_statement&pm=9975
- Suggested Reading
- Burnside Lemma, Polya’s theorem
- Generating functions
- Suggested Reading
- Herbert Wilf's generating functionology/
- Robert Sedgewick and Flajoulet's Combinatorial analysis
- Suggested Reading
- Basic
- Arrays/Stacks/Queues :
- Singly/Doubly Linked List :
- Problems
- Reading:
- CLRS: section 10.2
- Mark Allen Weiess Chapter 3
- Hash Tables :
- Problems
- Reading:
- CLRS: Chapter 11
- Mark Allen Weiess Chapter 5
- Circular linked list / queue
- Problems
- Binary/nary Trees
- Reading
- CLRS: Section 10.4
- CLRS: Chapter 12
- Mark Allen Weiess Chapter 4
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack
- Reading
- Heaps
- Problems
- Reading :
- Mark Allen Weiess Chapter 6
- Advanced
- Trie
- Problems
- Reading
- tbd
- Interval trees / Segment Trees
- Problems
- Reading
- tbd
- Fenwick(Binary Indexed) trees
- Disjoint data structures
- Problems
- Reading:
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure
- Mark Allen Weiess Chapter 8
- Range minimum Query(RMQ)
- Customized interval/segment trees (Augmented DS)
- Problems
- Reading:
- CLRS: Chapter 14 (augmented DS)
- AVL Trees
- Problems
- Reading
- tbd
- Trie
- Miscellaneous (Study on your own)
- Splay Trees
- B/B+ Trees
- k-d Trees
- Red-black Trees
- Skip List
- Binomial/Fibonacci heaps
- Exercises
- https://www.spoj.pl/problems/LAZYPROG/ (Hint: Heaps)
- https://www.spoj.pl/problems/HELPR2D2/ (Hint: Interval Trees)
- https://www.spoj.pl/problems/SAM/ (Hint: Heaps)
- https://www.spoj.pl/problems/PRHYME/ (Hint: Trie)
- https://www.spoj.pl/problems/HEAPULM/ (Hint: Interval Trees)
- https://www.spoj.pl/problems/CORNET/ (Hint: Disjoint )
- https://www.spoj.pl/problems/EXPAND/
- https://www.spoj.pl/problems/WPUZZLES/
- https://www.spoj.pl/problems/LIS2/
- Backtracking - [Beginner].
- Problems
- N queens problems
- Knight’s Tour
- Sudoku Problem
- Tiling Problem.
- 15 puzzle.
- Problems
- Dancing Links and Algorithm X given by Knuth - [Advanced]
- Problems
- PRLGAME, SUDOKU, NQUEEN on SPOJ
- Suggested reading -
- Problems
- 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 -
- Problems
- Ternary Search - [Intermediate].
- Problems
- http://www.spoj.pl/problems/KPPOLY/
- http://www.codechef.com/DEC09/problems/K1/
- http://www.topcoder.com/stat?c=problem_statement&pm=4705&rd=7993
- http://www.topcoder.com/stat?c=problem_statement&pm=7741&rd=10671
- http://www.topcoder.com/stat?c=problem_statement&pm=6464&rd=9994
- http://www.topcoder.com/stat?c=problem_statement&pm=3501&rd=6529
- http://www.topcoder.com/stat?c=problem_statement&pm=4567&rd=6539
- Problems
- Meet in the middle [Intermediate].
- Problems
- 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.
- Arithmetic Precision - [Beginner].
- Suggested Reading -
- Representing sets with bitmasks and manipulating bitmasks - [Beginner].
- Suggested Reading -
- Problems
- refer to the tutorial link in Suggested reading section.