Quora Feeds
Active Member
Okeke Arthur Ugochukwu
List of Topics for programming Competitions -
Area of Union of Circles.
Delayunay Triangulation of n points in O(n * logn).
Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm.
Point in a polygon problem -
Searching and preprocessing Regular Expressions consisting of ‘?’, ‘*’.
Multi-dimensional pattern matching.
Problems on Strings [can be solved with a variety of techniques] -
Strongly Connected Components.
Topological sort
Bellman-Ford algorithm.
Euler Tour/Path.
Hopcroft Karp bipartite matching algorithm.
Gomory-Hu Trees.
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
DP with datastructures
A good collection of problems
Greedy.
Number Theory.
Chinese remainder theorem
Stirling numbers
Wilson theorem
Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)
Syllabus
Syllabus
b. Singly/Doubly Linked List :
iii. Miscellaneous (Not to be covered)
iv. Exercices
Regular Iteration to reach a fixed point [Advanced].
See Questions On Quora
Continue reading...
List of Topics for programming Competitions -
- Basic Geometry/Euclidean Geometry/Coordinate Geometry/ [3-D variants of everything].
- Computational 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).
- Graham Scan algorithm for Convex Hull O(n * log(n)).
- Suggested Reading -
- Suggested Reading - Rotating Calipers
- Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.
- Area/Perimeter of Union of Rectangles.
- Closest pair of points.
- Suggested Reading -
Area of Union of Circles.
Delayunay Triangulation of n points in O(n * logn).
Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm.
Point in a polygon problem -
- O(n) solution without preprocessing.
- O(logn) algorithm with O(n * logn) preprocessing for convex polygons.
- 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.
- Computational Geometry: Algorithms and applications. Mark De Burg.
- KnuthMorrisPratt algorithm.
- Problems - NHAY, PERIOD on SPOJ.
- Suggested Reading -
- Cormen chapter on Strings.
- Introduction to String Searching Algorithms
- Problems - WPUZZLES on SPOJ.
- 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 Ukkenon’s algorithm.
- O(n) construction of Suffix Trees if provided with Suffix Arrays using Farach’s algorithm.
- O(n) Suffix Automaton construction.
- O(n * logn) method of DBF construction using Radix Sort.
Searching and preprocessing Regular Expressions consisting of ‘?’, ‘*’.
Multi-dimensional pattern matching.
Problems on Strings [can be solved with a variety of techniques] -
- 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
- 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 -
Strongly Connected Components.
- problems -
- problems -
- problems -
- SHPATH on SPOJ.
- problems -
- COURIER on SPOJ.
- problems -
- BLINNET on SPOJ.
Topological sort
Bellman-Ford algorithm.
Euler Tour/Path.
- problems - WORDS1 on SPOJ.
- Introduction to Graphs and Their Data Structures: Section 1.
- Also refer to the tutorial for problems concerning these techniques.
- Cormen chapter 22 to 24.
- Maximum flow using Ford Fulkerson Method.
- Suggested Reading -
- Maximum flow using Dinics Algorithm.
- Problems - PROFIT on spoj.
- Minimum Cost Maximum Flow.
- Successive Shortest path algorithm.
- Cycle Cancelling algorithm.
- Suggested Reading -
- problems - GREED, SCITIES, TOURS on SPOJ | Problem Statement
Hopcroft Karp bipartite matching algorithm.
- problems - ANGELS on SPOJ.
Gomory-Hu Trees.
- i) Problems - MCQUERY on Spoj.
- problems - Page on acm.uva.es
- Suggested Reading - Not found
- Network flow - Algorithms and Applications by Ahuja
- Cormen book chapter 25.
- Suggested Reading - Dynamic Programming(DP) as a tabulation method
- Cormen chapter on DP
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
DP with datastructures
- http://www.spoj.pl/problems/INCSEQ/
- SPOJ.com - Problem INCDSEQ
- http://www.spoj.pl/problems/LIS2/
- Problem Statement
A good collection of problems
Greedy.
- Suggested Reading -
- Chapter on Greedy algorithms in Cormen.
- Greedy is Good - topcoder
Number Theory.
- 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
- topcoder
- Problem 64 - Project Euler
- Problem 65 - Project Euler
- Problem 66 - Project Euler
- Problem Statement
- Problem Statement
- Suggested Reading
- 1.6, 2.2 from Number Theory by SY Yan
- 31.6 , 31.7 from Cormen
Chinese remainder theorem
- Suggested Reading
- 31.5 from Cormen
- 1.6 from Number Theory by SY Yan
- Project Euler 271
- Problem Statement
- Deterministic O(sqrt(n) ) approach
- Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test
- Suggested Reading -
- Primality Testing : Non-deterministic Algorithms
- Cormen 31.8
- 2.2 from Number Theory by SY Yan
- Primality Testing : Non-deterministic Algorithms
- Problems -
- PON, PRIC, SOLSTRAS on SPOJ
- Problem Statement
- PON, PRIC, SOLSTRAS on SPOJ
- Suggested Problems - PRIME1 on SPOJ
- Suggested Reading
- 31.2 Cormen
- GCD on SPOJ
- Problem H - GCD Extreme (I)
- Suggested Reading -
- Naive O(sqrt(n)) method
- Pollard Rho factorization
- Suggested Reading
- 2.3 from Number Theory SY Yan
- 31.9 Cormen
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
- Basic Number Theory Every Programmer Should Know...
- Category: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
- Suggested problems
- Suggested problems
- Special discrete and continuous probability distributions
- Bernoulli, Binomial, Poisson, normal distribution
- Suggested Problem
- Bernoulli, Binomial, Poisson, normal distribution
- Suggested Readings
- Cormen appendix C (very basic)
- Topcoder probabilty tutorial http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities
- Random variable
- Expected value
- William Feller, An introduction to probability theory and its applications
- Cormen appendix C (very basic)
- Counting
- Basic principles - Pigeon hole principle, addition, multiplication rules
- Suggested problems
- Suggested readings
- Inclusion-exclusion
- Suggested readings
- Suggested problems
- Suggested reading - Stirling, eurlerian, harmonic, bernoulli, fibonnacci numbers
- Stirling number
- Eulerian number
- Harmonic series (mathematics)
- Bernoulli number
- Fibonacci number
- Concrete mathematics by Knuth
- Stirling number
- Suggested problems
- Advanced counting techniques - Polya counting, burnsides lemma
- Suggested reading
- Suggested Problems
- Suggested reading
Syllabus
- Basic principles and Nim game
- Sprague grundy theorem, grundy numbers
- Suggested readings
- Suggested problems
- Suggested readings
- Suggested problems
Syllabus
- 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
- Cormen 28.2
- 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
- Problem Statement
- JPIX on Spoj
- Problem Statement
- Suggested Reading
- Determinant , Rank and Inverse of Matrix [ Gaussean Elimination , Gauss Jordan Elimination]
- Suggested Reading
- 28.4 Cormen
- Linear Algebra by Kenneth Chapter 1
- 28.4 Cormen
- Problems
- Problem Statement
- Problem Statement
- Problem Statement
- HIGH on Spoj
- Problem Statement
- Suggested Reading
- Solving system of linear equations
- Suggested Reading
- 28.3 Cormen
- Linear Algebra by Kenneth Chapter 1
- 28.3 Cormen
- Problems -
- Suggested Reading
- Using matrix exponentiation to solve recurrences
- Suggested Reading
- Problems
- REC, RABBIT1 , PLHOP on spoj
- Problem Statement , Problem Statement, Problem Statement
- REC, RABBIT1 , PLHOP on spoj
- Suggested Reading
- Eigen values and Eigen vectors
- Problems
- Problems
- Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]
- Problems
- Problem Statement
- POLYEQ , ROOTCIPH on Spoj
- Problem Statement
- Problems
- Lagrange Interpolation
- Problems
- Problems
- Suggested Reading
- Art of Computer Programming by Knuth Vol. 3
- ShuffleMethod, Permutation and WordGame on topcoder.
- Bernside Lemma, Polias theorem
- Suggested Reading
- Hernstein's topics in algebra
- Algorithms Weekly by Petr Mitrichev
- Hernstein's topics in algebra
- Problems
- TRANSP on spoj
- Problem Statement
- TRANSP on spoj
- Suggested Reading
- Herbert Wilf's generating functionology
- Robert Sedgewick and Flajoulet's Combinatorial analysis
- Data Structures.
- Basic
- Arrays/Stacks/Queues :
- Problems
- https://www.spoj.pl/problems/STPAR/
- https://www.spoj.pl/problems/SHOP/
- https://www.spoj.pl/problems/WATER/
- Reading:
- CLRS: section 10.1
- Minimum Cost Flow: Part Two - Algorithms
b. Singly/Doubly Linked List :
- Problems
- Reading: CLRS: section 10.2, Mark Allen Weies Chapter 3
- Problems
- Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5
- Problems
- Reading
- CLRS: section 10.4
- CLRS: Chapter 12
- Mark Allen Weies Chapter 4
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack
- Problems
- Reading : Mark Allen Weies Chapter 6
- Trie (Keyword tree)
- Problems
- Reading
- Interval trees / Segment Trees
- Problems
- Reading
- Fenwick(Binary Indexed) trees
- Problems
- Reading: Binary Indexed Trees
- Disjoint data structures
- Problems
- Reading:
- Disjoint-set Data Structures
- Mark Allen Weies Chapter 8
- Range minimum Query(RMQ)
- Problems
- Customized interval/segment trees (Augmented DS)
- Problems
- Reading: CLRS: Chapter 14 (augmented DS)
- Problems
- Reading
iii. Miscellaneous (Not to be covered)
- Splay Trees
- B/B+ Trees
- k-d Trees
- Red-black Trees
- Skip List
- Binomial/ Fibonacci heaps
iv. Exercices
- https://www.spoj.pl/problems/LAZ.../ (Hint: Heaps)t
- SPOJ.com - Problem HELPR2D2 (Hint: Interval Trees)
- https://www.spoj.pl/problems/SAM/ (Hint: Heaps)
- SPOJ.com - Problem PRHYME (Hint: Trie)
- SPOJ.com - Problem HEAPULM (Hint: Interval Trees)
- SPOJ.com - Problem CORNET (Hint: Disjoint )
- SPOJ.com - Problem EXPAND
- SPOJ.com - Problem WPUZZLES
- https://www.spoj.pl/problems/LIS2/
- Search Techniques/Bruteforce writing techniques/Randomized algorithms.
- Backtracking - [Beginner].
- problems ->
- N queens problems
- Knights Tour
- Sudoku Problem
- Tiling Problem.
- 15 puzzle.
- problems - PRLGAME, SUDOKU, NQUEEN on SPOJ
- Suggested reading -
- poblems - AGGRCOW on SPOJ. Refer the tutorial for more problems.
- finding all real roots of a polynomial using binary search. [intermediate].
- Suggested Reading -
- problems -
- http://www.spoj.pl/problems/KPPOLY/
- Plant Location
- Problem Statement
- Problem Statement
- Problem Statement
- Problem Statement
- Problem Statement
- problems -
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.
- Quick-Sort.
- Arithmetic Precision - [Beginner].
- Suggested Reading -
- Representing sets with bitmasks and manipulating bitmasks - [Beginner].
- Suggested Reading -
See Questions On Quora
Continue reading...