Collection of material for competitive programming

As promised by me and Noureldin Yosri, we collected a lot of topics with resources and problems that cover a variety of Mathematics/Geometry topics. Ahmad Elsagheer also helped us collect some of the geometry materials.

The post has sections, each consists of a list of topics followed by some sources/problems.

Important related books

• A simple book I personally read a long time ago that prepared me for mathematical thinking and understanding How to think like a mathematician, kevin houston.
• MIT Mathematics for CS course
• Concrete Mathematics (chapters 1-4) by Donald Knuth, these chapters are full of algebraic and mathematical tricks and interesting problems, also a chapter including a variety of number theory topics.
• Art and craft of problem-solving by Paul Zeitz, a revolutionary book about problem-solving and thinking.
• Introduction to Algorithms, Cormen (chapters 31, 33)
• Introduction to Mathematical Thinking Keith Devlin.

Number theory topics

• Fundamental theorem of arithmetic
• Modular Arithmetic
• Sieve of Eratosthenes
• Binary exponentiation
• Variants of sieve-like algorithms to compute various multiplicative functions, like the sum of divisors, number of divisors, smallest prime divisor and Euler totient function.
• Bezout's identity, Greatest common divisor, Extended Euclidean algorithm
• Integer factorization
• Pollard rho for large integer factorization
• Primality Testing
• Group theory basics
• Lagrange's theorem (group theory)
• Fermat's little theorem and its generalization Euler's theorem.
• Primitive roots of unity
• Discrete logarithm using Baby-step Giant-step algorithm
• Multiplicative functions Mobius inversion, also equation 4.61, section 9, chapter 4, concrete mathematics.

• Chinese remainder theorem, generalized with diophantine equations

  • Lecture: Advanced Data Structures and Algorithms, Part 1
  • Lecture: Advanced Data Structures and Algorithms, Part 2

• Diophantine equations

• Combinatorial arguments (also Art and Craft of Problem solving chapter 6)
• Basic combinatorics functions, Stirling, Catalan (Concrete mathematics chapters 5, 6)
• Generating functions

Problems

• LCS
• PRIME1
• APS
• CPRIME
• CUBEFR
• DIV
• DIVFACT
• DIVSUM
• ETF
• FACT0
• FACT1
• FRQPRIME
• SKEY
• AMATH
• GCDEX
• VLATTICE
• INTEGER1
• GMLIFE
• DISCRT
• LCMSUM
• GMLIFE
• GMLIFE
• Boring Card Game
• Pythagorean Triples
• SMPLSUM
• UVA: 5879

More number theory topics

• Pythagorean triples
• Fermat's theorem on sums of two squares and Gaussian integers.
• Gaussian diophantine equations
• Quadratic residue (Square root mod prime)
• Number theoretic transform NTT (a variant of FFT)
• Solving linear recurrences

Geometry

• Basic 2d geometry (Book about geometry): Kiselev's Geometry: Book I. Planimetry
• USACO Geometry
• Geometry Topics/Algorithms:
  • Algorithms on polygons (convex hull, polygon cut, point in polygon O(log n), max triangle area in convex polygon)
  • Algorithms on circles (line-circle intersect, circle-circle intersect, geometric inversion, common tangents)
  • Vornoi diagrams
  • Line/Circle sweep

Others

• Newton’s method
• Factorial number system (for representation of permutations)
• Chapters 2, 3 in Art and Craft of Problem solving
• Calculus
• Linear Algebra
  • Gauss or Gauss-Jordan elimination
  • Gauss or Gauss-Jordan elimination mod prime
  • Eigenvalues and Eigenvectors
  • Matrix inverse
  • Determinants mod prime
  • Simplex (Linear programming)

YouTube channel explaining some of these topics: YouTube Playlist

Created on 2017-12-01 at 15:55