Jul 21, 2018

What are the mathematical knowledge necessary for competitive programming?

Image: What are the mathematical knowledge necessary for competitive programming?

The relationship between Computer Science and Mathematics

    Math is one of the foundations of computer sciences. So how is mathematics really applied in computer science? Despite advanced mathematics not applied frequently, basic mathematics, most importantly algebra, is the main ingredient for a successful computer scientist. 

    Many of the functions and operators in all programming languages require some knowledge of mathematics. For example, these operators include arithmetic, comparison, logical, assignment and conditional operators. All of the aforementioned tasks need mathematics for them to be used and properly applied, especially the arithmetic and conditional operators. 

    Competitive Programming heavily relies on algorithms, which the latter in turn heavily relies on mathematics. ‘Theoretical computer science’ strongly involves:

  • Arithmetic and Geometry
  • Discrete structures
  • Probability Theory
  • Linear Algebra
  • Matrices
  • Fast-Fourier Transform

Mathematics necessary for Competitive Programming:

Arithmetic and Geometry:

  1. Integers, operations(including exponentiation), comparison
  2. The basic property of integers(sign, parity, divisibility)
  3. Basic modular arithmetic(addition, subtraction, multiplication, division)
  4. Prime numbers and partition theory(Its a vast topic)
  5. Fractions and percentages
  6. Line, line segment, angle, triangle, rectangle, square, circle(and especially way to represent them in your code)
  7. Points, vector, coordinates in a plane
  8. Polygon(vertex, side/edge, simple, convex, inside, area)
  9. Euclidean distances
  10. Pythagorean theorem(There are the diverse use of this theorem)
  11. In some questions, you might need Fermat’s Little Theorem, Chinese remainder theorem, or may need to use the Euler function etc. You need to get better in number theory. I have encountered some problems on CodeChef which need these myself.
  12. Knowing some techniques like Euclidean Algorithm and fast exponentiation are considered to be a prerequisite in some contests.
  13. Some computational geometry techniques like Graham Scan and convex hull.

Discrete Structures:

  1. Functions, Relations, and Sets
    • Functions(surjections, injections, inverses, composition)
    • Relations(reflexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order)
    • Sets(cardinality, inclusion/exclusion, complements, Cartesian products, power sets)
  2. Basic Logic
    • First-order logic
    • Logical connectives(including their basic properties)
    • Truth Tables
    • Universal and Existential quantification
    • Modus ponens and Modus tollens(Not to get intimidated by the names :P)
  3. Proof techniques(You don’t need them too rigorously)
  4. Basics of Counting
    • Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)
    • Permutations and combinations (basic definitions)
    • Factorial function, binomial coefficients
    • Inclusion-exclusion principle
    • Pigeonhole principle
    • Pascal’s identity, Binomial theorem
    • Solving recurrence relations
    • Burnside Lemma
  5. Graphs and trees
    • Trees and their basic properties, rooted trees
    • Undirected graphs (degree, path, cycle, connectedness, Euler/Hamilton path/cycle, handshaking lemma)
    • Directed graphs (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle)
    • Spanning trees
    • Traversal strategies
    • ‘Decorated’ graphs with edge/node labels, weights, colors
    • Multigraphs, graphs with self-loops
    • Bipartite graphs
    • Planar graphs

Probability theory

Linear Algebra

Matrices

  1. Matrix multiplication
  2. Matrix exponentiation
  3. Matrix inversion
  4. Gaussian elimination

Fast Fourier transform

Even though many of these topics need not be mastered rigorously, some are prerequisites and competitive programmers should have the basic knowledge of at least most of them to be among the top tier of programmers.

This Article is heavily inspired from this Quora thread



Leave a Reply :

Captcha

Comments :

Anonymous
Thank you, Sir