Mathematics

Goldbach's conjecture has been verified for every even integer up to 4 * 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a hundred unit tests and still fail on the empty list or the input size your tests never reached. **Basic Proof Techniques** equips you with the small set of argument styles that turn intuition into certainty about correctness, complexity bounds, and data structure invariants. Direct proof chains definitions and prior facts to a claim. Proof by contradiction assumes the opposite and derives a logical impossibility, as in the irrationality of `sqrt(2)` and the `Omega(n log n)` lower bound for comparison sorts. Mathematical induction, in weak and strong forms, proves statements over the natural numbers via a base case and an inductive step, the backbone of recurrence solutions and loop invariants. Proof by contraposition swaps `P implies Q` for the equivalent `not Q implies not P`, and proof by cases breaks a claim into exhaustive subcases. This lesson builds on **Discrete Mathematics Basics**, where you met sets, propositional logic, implications, and the first taste of formal proof. Here those informal sketches become the disciplined patterns that algorithm analysis, theoretical CS, and clean engineering arguments all rely on. With proofs in hand, you have completed the foundations track and are ready to step into **Arrays & Strings** and the rest of the data structures curriculum, armed to analyze every operation rigorously.

How many ways can you arrange `n` items? How many subsets does a set of size `n` have? Questions like these are not idle puzzles, they are exactly the questions you have to answer to know whether a brute-force solution will run in milliseconds or in millennia. **Combinatorics Basics** gives you the counting tools that turn vague statements like "try every possibility" into precise complexity claims. This lesson covers the four counting ideas you will rely on throughout DSA. The **rule of sum** and **rule of product** let you decompose multi-step processes and count outcomes; **permutations** count ordered arrangements (`n!` for arranging all of them, `nPr` for choosing `r` in order); **combinations** count unordered selections (`nCr`, also written as binomial coefficients); and **Pascal's triangle** plus a first look at **basic probability** tie everything together. You will see why a set of size `n` has `2^n` subsets, why generating all permutations of an array is `O(n!)`, and how counting principles directly produce the time complexity of backtracking algorithms. This lesson builds on **Discrete Mathematics Basics**, where you formalized sets, set operations, and logic. Combinatorics is what happens when you start asking "how many?" about those sets, ordered or unordered, with or without repetition. With the counting toolkit in place you will continue the math track in **Number Theory Fundamentals**, picking up primes, divisibility, and `gcd`, the other half of the math you need for hashing, cryptography-style problems, and modular arithmetic.

Almost every conditional you have ever written is a tiny piece of propositional logic, and almost every collection you have ever stored is, mathematically, a set. **Discrete Mathematics Basics** makes that connection explicit, giving you the formal vocabulary that data structures, graph algorithms, database queries, and correctness arguments all sit on top of. This lesson walks you through three pillars of discrete math used throughout DSA. First, **sets** and the operations on them: union, intersection, difference, complement, subset, and membership, the same ideas baked into hash sets and array problems. Second, **propositional logic**: the operators `AND`, `OR`, `NOT`, and implication, plus truth tables for evaluating compound expressions; this is the math behind every Boolean condition in your code. Third, **binary relations** and their properties (reflexive, symmetric, transitive), which generalize the way edges connect nodes in graphs and rows connect in databases. Along the way you will get a first taste of formal proof: how to argue that two sets are equal or that a logical equivalence always holds. This lesson assumes only basic programming familiarity, so no specific DSA prerequisite is required. If you have written `if (x && !y)` or used a hash set, you already have informal intuition for everything we will formalize here. From here you will move into **Combinatorics Basics**, where you will use these set and counting foundations to count permutations, combinations, and arrangements (the math behind backtracking and many complexity proofs).

How can a search through a million sorted items finish in roughly twenty comparisons? The answer is `log_2(n)`, and once you internalize what that expression really means, an entire family of fast algorithms (binary search, balanced trees, divide-and-conquer) suddenly stops feeling like magic. **Logarithms & Exponentiation** builds your intuition for the math behind `O(log n)`. You will start from a concrete framing (a logarithm answers the question "how many times can I halve `n` before reaching 1?") and work through the powers-of-2 sequence (1, 2, 4, 8, 16, ...) that appears constantly in computer science. You will pick up the three logarithm properties you actually need (`log(a * b) = log(a) + log(b)`, `log(a^n) = n * log(a)`, and `log(1) = 0`), see why the base does not matter inside Big-O, meet fast exponentiation as a preview of `O(log n)` in action, and trace why every halving loop produces logarithmic complexity. In **Big-O Notation (Upper Bound)**, you learned that `O(log n)` sits between `O(1)` and `O(n)` in the hierarchy and is associated with algorithms that halve their work each step. This lesson supplies the mathematical reason that pattern produces a logarithm, so the complexity class stops being something you memorize and starts being something you can derive. Once logarithms feel comfortable, you will be ready for **Mathematical Sequences**, where you will study arithmetic sums, geometric series, and Fibonacci patterns that explain the running times of everything from nested loops to recursive algorithms.

Why is a triangular nested loop that does `1 + 2 + 3 + ... + n` units of work classified as `O(n^2)` rather than `O(n)`? Because the closed form of that sum is `n(n+1)/2`, which grows quadratically. The same kind of summation argument explains why merge sort is `O(n log n)`, why a doubling array gives amortized `O(1)` insertions, and why naive recursive Fibonacci is exponentially slow. **Mathematical Sequences** equips you with the essential sequences and summation formulas behind algorithm analysis. You will work with arithmetic sequences (where each term adds a constant) and the formula `1 + 2 + ... + n = n(n+1)/2`, geometric sequences (where each term multiplies by a constant ratio) and their geometric-series sum, and the Fibonacci sequence defined by `F(n) = F(n-1) + F(n-2)`. You will then connect these formulas back to code: triangular nested loops, halving-and-doubling patterns, and the canonical recursive Fibonacci that motivates dynamic programming. In **Big-O Notation (Upper Bound)**, you learned to spot dominant terms and to drop constants and lower-order terms. This lesson supplies the closed-form summations that turn a step count like `1 + 2 + ... + n` into a precise polynomial you can simplify with confidence. With these summation tools in hand, you will be ready for **Debugging by Tracing**, where you will sharpen the step-by-step execution skills you need to verify that the algorithms you analyze actually behave the way your formulas predict.

Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo `10^9 + 7`", and you will find the same machinery underneath: **modular arithmetic**, the math of working with remainders rather than full integers. It is the bridge between number theory and a huge swath of real algorithms. This lesson develops that machinery from first principles. You will revisit the `mod` operation precisely (including its relationship to division and remainders), then prove and use the addition, subtraction, and multiplication rules that let you take `mod` at every step of a long calculation without changing the answer. From there you will implement **fast modular exponentiation** in `O(log n)` time using binary exponentiation, compute **modular inverses** with **Fermat's Little Theorem** when the modulus is prime, and see exactly why hash tables, RSA, and contest problems rely on these tricks to avoid overflow and to invert multiplications. This lesson builds on **Number Theory Fundamentals**, where you learned about primes, divisibility, `gcd`, and the Euclidean algorithm. Modular arithmetic uses all of those: primality lets you apply Fermat, `gcd` decides when an inverse exists, and divisibility underlies every congruence. From here the only foundations topic remaining is **Basic Proof Techniques**, where you will learn the proof tools (induction, contradiction, contraposition) that make the kinds of arguments you have just been waving at fully rigorous.

Why are hash table sizes almost always prime? Why does the Euclidean algorithm for `gcd` run in `O(log(min(a, b)))` time despite using only subtraction or remainders? **Number Theory Fundamentals** is the branch of math that answers these questions and quietly powers a surprising amount of practical software, from hashing and cryptography to scheduling and competitive programming shortcuts. This lesson introduces the core building blocks. You will study **prime numbers** and how to test primality efficiently, the **divisibility** relation and quick rules for spotting divisors, **GCD** (greatest common divisor) and **LCM** (least common multiple) with the identity `lcm(a, b) = a * b / gcd(a, b)`, and the **Euclidean algorithm** for computing `gcd` in logarithmic time. You will also do **prime factorization** by trial division (`O(sqrt(n))`) and see how factorizations make divisor counting, simplification, and periodicity arguments straightforward. This lesson builds on **Discrete Mathematics Basics**, where you learned how to reason precisely about sets, relations, and logical claims. Number theory uses that same proof-style reasoning, but applied to the integers and their multiplicative structure. With primes, `gcd`, and factorization in your toolkit, you will be ready to take the premium step into **Modular Arithmetic**, where you will reuse all of these ideas to work with `mod`, modular inverses, and Fermat's Little Theorem.

Computing `a^b mod m` for `a = 7`, `b = 10^18`, and `m = 10^9 + 7` looks impossible: even iterating one multiplication per step would take longer than the age of the universe. Binary exponentiation does it in 60 multiplications, by squaring the base while halving the exponent. RSA encryption depends on exactly this trick, and so do most modular-arithmetic problems in competitive programming. **Mathematical Algorithms** assembles the standard toolkit. You will implement the Sieve of Eratosthenes for primes up to `N` in `O(N log log N)`, plus the segmented sieve for large ranges. Binary exponentiation handles `a^b mod m` in `O(log b)`, and the matrix-exponentiation generalization computes Fibonacci or any linear recurrence in `O(log n)`. You will derive the Extended Euclidean algorithm for `ax + by = gcd(a, b)` and use it for modular inverses, walk through the Chinese Remainder Theorem, compute Euler's totient, apply Fermat's Little Theorem to modular inversion, and run the Miller-Rabin probabilistic primality test. In **Number Theory Fundamentals**, you saw GCD, primes, and divisibility. **Modular Arithmetic** introduced congruences and modular inverses. This lesson turns those facts into algorithms that scale to numbers the problem statement actually asks about. Next, **Computational Geometry** turns to algorithmic problems on points, lines, and polygons.