What's a complete list of topics/a complete syllabus to fully learn computer programming...

[Quora Feeds]

Okeke Arthur Ugochukwu

List of Topics for programming Competitions -

1. Basic Geometry/Euclidean Geometry/Coordinate Geometry/ [3-D variants of everything].
   
2. Computational Geometry.
   
   1. Graham Scan algorithm for Convex Hull O(n * log(n)).
      
   2. Online construction of 3-D convex hull in O(n^2).
      
   3. Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn).

• Suggested Reading -

1. Intersections of a Set of Segments

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 -

1. Line Sweep Algorithms

Problems - Follow the tutorial for list of problems.
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.

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

1. KnuthMorrisPratt algorithm.

• Problems - NHAY, PERIOD on SPOJ.
  
• Suggested Reading -

1. Cormen chapter on Strings.
   
2. Introduction to String Searching Algorithms

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 Ukkenon’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.

Manachar’s algorithm to find Lengh 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 [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

Basic Graphs [beginner].

1. Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios.
   
2. Breadth First Search.

• problems -

1. PPATH, ONEZERO, WATER on SPOJ

Depth First Search.
Strongly Connected Components.

• problems -

1. TOUR and BOTTOM on SPOJ.

Biconnected Components, Finding articulation points and bridges].

• problems -

1. RELINETS, PT07A on SPOJ.

Dijkstra algorithm -

• problems -

1. SHPATH on SPOJ.

Floyd Warshall algorithm -

• problems -

1. COURIER on SPOJ.

Minimum Spanning Tree

• problems -

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

• Introduction to Graphs and Their Data Structures: Section 1.
  
• Also refer to the tutorial for problems concerning these techniques.
  
• Cormen chapter 22 to 24.

Flow networks/ matching etc etc. [Interdiate/Advanced].

1. Maximum flow using Ford Fulkerson Method.

• Suggested Reading -

1. 1. 1. Maximum Flow: Augmenting Path Algorithms Comparison
   2. problems - TAXI, POTHOLE, IM, QUEST4, MUDDY, EN, CABLETV, STEAD, NETADMIN, COCONUTS, OPTM on SPOJ.
2. Maximum flow using Dinics Algorithm.

• Problems - PROFIT on spoj.

1. Minimum Cost Maximum Flow.

• Successive Shortest path algorithm.
  
• Cycle Cancelling algorithm.
  
• Suggested Reading -

1. Minimum Cost Flow: Part One - Key Concepts

Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/Hungarian Method)

• problems - GREED, SCITIES, TOURS on SPOJ | Problem Statement

Stoer Wagner min-cut algorithm.
Hopcroft Karp bipartite matching algorithm.

• problems - ANGELS on SPOJ.

Maximum matching in general graph (blossom shrinking)
Gomory-Hu Trees.

• i) Problems - MCQUERY on Spoj.

Chinese Postman Problem.

• problems - Page on acm.uva.es
  
• Suggested Reading - Not found

Suggested Reading for the full category ->

• Network flow - Algorithms and Applications by Ahuja
  
• Cormen book chapter 25.

Dynamic Programming.

1. Suggested Reading - Dynamic Programming(DP) as a tabulation method

• Cormen chapter on DP

Standard problems (you should really feel comfortable with these types)

• Problem Statement
  
• Problem Statement

State space reduction

• Problem Statement
  
• Problem Statement
  
• Problem Statement

Solving in the reverse - easier characterizations looking from the end

• http://www.spoj.pl/problems/MUSKET/
  
• Problem Statement

Counting/optimizing arrangements satisfying some specified properties

• Problem Statement
  
• Problem Statement

Strategies and expected values

• Problem Statement
  
• Problem Statement
  
• Problem Statement
  
• Problem Statement

DP on probability spaces

• Problem Statement
  
• Problem Statement
  
• Problem Statement

DP on trees

• Problem Statement
  
• Problem Statement
  
• TopCoder | Login

DP with datastructures

• http://www.spoj.pl/problems/INCSEQ/
  
• SPOJ.com - Problem INCDSEQ
  
• http://www.spoj.pl/problems/LIS2/
  
• Problem Statement

Symmetric characterization of DP state

• Problem Statement

A good collection of problems

• Dynamic Programming Type - Codeforces
  
• Page on appspot.com

Greedy.

1. Suggested Reading -

• Chapter on Greedy algorithms in Cormen.
  
• Greedy is Good - topcoder

problems - refer to the topcoder tutorial.
Number Theory.

1. Modulus arithmetic - basic postulates [Including modular linear equations , Continued fraction and Pell's equation]

• Suggested Reading -

1. Chapter 1 from Number Theory for Computing by SY Yan [ Recommended ]
   
2. 31.1, 31.3 and 31.4 from Cormen
   
3. topcoder

Problems

1. Problem 64 - Project Euler
   
2. Problem 65 - Project Euler
   
3. Problem 66 - Project Euler
   
4. Problem Statement
   
5. Problem Statement

Fermat's theorem, Euler Totient theorem ( totient function, order , primitive roots )

• Suggested Reading

1. 1.6, 2.2 from Number Theory by SY Yan
   
2. 31.6 , 31.7 from Cormen

Problems

1. Problem 70 - Project Euler
   
2. SPOJ.com - Problem NDIVPHI

Chinese remainder theorem

• Suggested Reading

1. 31.5 from Cormen
   
2. 1.6 from Number Theory by SY Yan

Problems

1. Project Euler 271
   
2. Problem Statement

Primality tests -

• Deterministic O(sqrt(n) ) approach
  
• Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test

1. Suggested Reading -
   
   1. Primality Testing : Non-deterministic Algorithms
      
   2. Cormen 31.8
      
   3. 2.2 from Number Theory by SY Yan
2. Problems -
   
   1. PON, PRIC, SOLSTRAS on SPOJ
      
   2. Problem Statement

Prime generation techniques - Sieve of Erastothenes

• Suggested Problems - PRIME1 on SPOJ

GCD using euclidean method

• Suggested Reading

1. 31.2 Cormen

Problems -

1. GCD on SPOJ
   
2. Problem H - GCD Extreme (I)

Logarithmic Exponentiation

• Suggested Reading -

1. Primality Testing : Non-deterministic Algorithms

Integer Factorization

• Naive O(sqrt(n)) method
  
• Pollard Rho factorization
  
• Suggested Reading

1. 2.3 from Number Theory SY Yan
   
2. 31.9 Cormen

Problems -

1. Problem Statement
   
2. SPOJ.com - Problem DIVSUM2
   
3. Problem Statement

Stirling numbers
Wilson theorem

• nCr % p in O(p) preprocess and O(log n ) query

1. Lucas Theorem
   
2. 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

Problems on Number Theory -

• Category:Number Theory
  
• Page on appspot.com

Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)

1. Probability.

Syllabus

• Basic probability and Conditional probability

1. Suggested problems

1. http://www.spoj.pl/problems/CT16E/
   
2. SPOJ.com - Problem CHICAGO

• Random variables, probability generating functions
  
• Mathematical expectation + Linearity of expectation

1. 1. Suggested problems
      
      1. SPOJ.com - Problem FAVDICE
         
      2. Problem Statement
2. Special discrete and continuous probability distributions
   
   1. Bernoulli, Binomial, Poisson, normal distribution
      
   2. Suggested Problem
      
      1. SSU Online Contester :: 498. Coins
3. Suggested Readings
   
   1. Cormen appendix C (very basic)
      
   2. Topcoder probabilty tutorial http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities
      
   3. Random variable
      
   4. Expected value
      
   5. William Feller, An introduction to probability theory and its applications

1. Counting

Syllabus

• Basic principles - Pigeon hole principle, addition, multiplication rules

1. Suggested problems

1. 1. http://acm.timus.ru/problem.aspx...
      
   2. Problem Statement
2. Suggested readings
   
   1. Combinatorial principles
      
   2. Page on topcoder.com
      
   3. Page on maa.org

• Inclusion-exclusion

1. Suggested readings
   
   1. Inclusion–exclusion principle
2. Suggested problems
   
   1. Problem Statement
      
   2. Problem Statement

Special numbers

1. Suggested reading - Stirling, eurlerian, harmonic, bernoulli, fibonnacci numbers
   
   1. Stirling number
      
   2. Eulerian number
      
   3. Harmonic series (mathematics)
      
   4. Bernoulli number
      
   5. Fibonacci number
      
   6. Concrete mathematics by Knuth
2. Suggested problems

1. 1. Problem Statement
      
   2. Problem Statement
      
   3. Problem Statement
      
   4. Problem Statement
2. Advanced counting techniques - Polya counting, burnsides lemma
   
   1. Suggested reading
      
      1. Burnside's lemma
         
      2. Algorithms Weekly by Petr Mitrichev
   2. Suggested Problems
      
      1. Problem Statement
         
      2. http://www.spoj.pl/problems/TRANSP/

c. Game theory
Syllabus

• Basic principles and Nim game

1. Sprague grundy theorem, grundy numbers
   
2. Suggested readings
   
   1. Sprague–Grundy theorem
      
   2. Algorithm Games - topcoder
      
   3. Feature Column from the AMS
      
   4. Page on codechef.com
3. Suggested problems
   
   1. Problem Statement
      
   2. Problem Statement

Hackenbush

1. Suggested readings
   
   1. Hackenbush
      
   2. Feature Column from the AMS
2. Suggested problems
   
   1. Computing + Mathematical Sciences
      
   2. http://www.spoj.pl/problems/PT07A/

d. Linear Algebra
Syllabus

• Matrix Operations

1. Addition and subtraction of matrices
   
   1. Suggested Reading
      
      1. Cormen 28.1
2. Multiplication ( Strassen's algorithm ), logarithmic exponentiation
   
   1. Suggested reading
      
      1. Cormen 28.2
         
      2. Linear Algebra by Kenneth Hoffman Section 1.6
   2. Problems
      
      1. Contest of Newbies 2006
3. Matrix transformations [ Transpose, Rotation of Matrix, Representing Linear transformations using matrix ]
   
   1. Suggested Reading
      
      1. Linear Algebra By Kenneth Hoffman Section 3.1,3.2,3.4,3.7
   2. Problems
      
      1. Problem Statement
         
      2. JPIX on Spoj
4. Determinant , Rank and Inverse of Matrix [ Gaussean Elimination , Gauss Jordan Elimination]
   
   1. Suggested Reading
      
      1. 28.4 Cormen
         
      2. Linear Algebra by Kenneth Chapter 1
   2. Problems
      
      1. Problem Statement
         
      2. Problem Statement
         
      3. Problem Statement
         
      4. HIGH on Spoj
5. Solving system of linear equations
   
   1. Suggested Reading
      
      1. 28.3 Cormen
         
      2. Linear Algebra by Kenneth Chapter 1
   2. Problems -
      
      1. Problem Statement
6. Using matrix exponentiation to solve recurrences
   
   1. Suggested Reading
      
      1. TopCoder Feature Articles
   2. Problems
      
      1. REC, RABBIT1 , PLHOP on spoj
         
      2. Problem Statement , Problem Statement, Problem Statement
7. Eigen values and Eigen vectors
   
   1. Problems
      
      1. Problem Statement

Polynomials

1. Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]
   
   1. Problems
      
      1. Problem Statement
         
      2. POLYEQ , ROOTCIPH on Spoj
2. Lagrange Interpolation
   
   1. Problems
      
      1. Problem Statement
         
      2. Problem Statement

e. Permutation cycles

• Suggested Reading

1. Art of Computer Programming by Knuth Vol. 3

Problems

1. ShuffleMethod, Permutation and WordGame on topcoder.

f. Group Theory

• Bernside Lemma, Polias theorem

1. Suggested Reading
   
   1. Hernstein's topics in algebra
      
   2. Algorithms Weekly by Petr Mitrichev
2. Problems
   
   1. TRANSP on spoj
      
   2. Problem Statement

Generating functions

• Suggested Reading

1. Herbert Wilf's generating functionology
   
2. Robert Sedgewick and Flajoulet's Combinatorial analysis

1. Data Structures.

1. Basic

1. Arrays/Stacks/Queues :

• Problems

1. https://www.spoj.pl/problems/STPAR/
   
2. https://www.spoj.pl/problems/SHOP/
   
3. https://www.spoj.pl/problems/WATER/

• Reading:

1. CLRS: section 10.1
   
2. Minimum Cost Flow: Part Two - Algorithms

b. Singly/Doubly Linked List :

• Problems

1. https://www.spoj.pl/problems/POSTERS/

• Reading: CLRS: section 10.2, Mark Allen Weies Chapter 3

c. Hash Tables :

• Problems

1. SPOJ.com - Problem HASHIT
   
2. SPOJ.com - Problem CUCKOO

• Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5

d. Circular linked list / queue

• Problems

1. SPOJ.com - Problem CTRICK

e. Binary/nary Trees

• Reading

1. CLRS: section 10.4
   
2. CLRS: Chapter 12
   
3. Mark Allen Weies Chapter 4
   
4. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack

f. Heaps

• Problems

1. https://www.spoj.pl/problems/PRO/
   
2. https://www.spoj.pl/problems/EXPEDI/

• Reading : Mark Allen Weies Chapter 6

ii. Advanced

1. Trie (Keyword tree)

• Problems

1. SPOJ.com - Problem MORSE
   
2. SPOJ.com - Problem EMOTICON

• Reading

1. Interval trees / Segment Trees

• Problems

1. SPOJ.com - Problem ORDERS
   
2. SPOJ.com - Problem FREQUENT

• Reading

1. Fenwick(Binary Indexed) trees

• Problems

1. SPOJ.com - Problem MATSUM

• Reading: Binary Indexed Trees

1. Disjoint data structures

• Problems

1. SPOJ.com - Problem BLINNET
   
2. https://www.spoj.pl/problems/CHAIN/

• Reading:

1. Disjoint-set Data Structures
   
2. Mark Allen Weies Chapter 8

1. Range minimum Query(RMQ)

• Problems

1. https://www.spoj.pl/problems/GSS1/

• Reading Range Minimum Query and Lowest Common Ancestor

1. Customized interval/segment trees (Augmented DS)

• Problems

1. https://www.spoj.pl/problems/GSS3/
   
2. SPOJ.com - Problem RRSCHED

• Reading: CLRS: Chapter 14 (augmented DS)

g. AVL Trees

• Problems

1. SPOJ.com - Problem ORDERS

• Reading

iii. Miscellaneous (Not to be covered)

1. Splay Trees
   
2. B/B+ Trees
   
3. k-d Trees
   
4. Red-black Trees
   
5. Skip List
   
6. Binomial/ Fibonacci heaps

iv. Exercices

1. https://www.spoj.pl/problems/LAZ.../ (Hint: Heaps)t
   
2. SPOJ.com - Problem HELPR2D2 (Hint: Interval Trees)
   
3. https://www.spoj.pl/problems/SAM/ (Hint: Heaps)
   
4. SPOJ.com - Problem PRHYME (Hint: Trie)
   
5. SPOJ.com - Problem HEAPULM (Hint: Interval Trees)
   
6. SPOJ.com - Problem CORNET (Hint: Disjoint )
   
7. SPOJ.com - Problem EXPAND
   
8. SPOJ.com - Problem WPUZZLES
   
9. https://www.spoj.pl/problems/LIS2/

1. Search Techniques/Bruteforce writing techniques/Randomized algorithms.
   
   1. Backtracking - [Beginner].

• problems ->

1. N queens problems
   
2. Knights Tour
   
3. Sudoku Problem
   
4. Tiling Problem.
   
5. 15 puzzle.

Dancing Links and Algorithm X given by Knuth - [Advanced]

• problems - PRLGAME, SUDOKU, NQUEEN on SPOJ
  
• Suggested reading -

1. Page on stanford.edu

Binary Search - [Beginner].

• poblems - AGGRCOW on SPOJ. Refer the tutorial for more problems.
  
• finding all real roots of a polynomial using binary search. [intermediate].
  
• Suggested Reading -

1. Binary Search - topcoder

Ternary Search - [Intermediate].

• problems -

1. http://www.spoj.pl/problems/KPPOLY/
   
2. Plant Location
   
3. Problem Statement
   
4. Problem Statement
   
5. Problem Statement
   
6. Problem Statement
   
7. Problem Statement

Meet in the middle [Intermediate].

• problems -

1. SPOJ.com - Problem MAXISET
   
2. Problems :: Show Problem

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.

Randomized Algorithms [Intermediate]-

• Quick-Sort.

General programming issues in contests ->

1. Arithmetic Precision - [Beginner].

• Suggested Reading -

1. 1. Representation of Integers and Reals: Section 1
2. Representing sets with bitmasks and manipulating bitmasks - [Beginner].

• Suggested Reading -

1. Page on topcoder.com

problems - refer to the tutorial link in Suggested reading section.

See Questions On Quora

Continue reading...