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