Algorithm
The Power of Binary Search
Binary search is ubiquitous. Even if you are not aware of it, you have most likely used some (approximate) version of binary search one way or another
Haris Angelidakis
Probability Theory
Concentration of Measure: The Glorious Chernoff Bound
..and how to derive it
Factorials
Factorials and How to Compute Them
I am sure you all remember the surprise you had the first time you saw a “5!” or “7!”
Number Theory
Euclid’s Algorithm for Computing the Greatest Common Divisor
An algorithm from ancient Greece
Linear Algebra
Matrix Multiplication and the Ingenious Strassen’s Algorithm
How Divide-And-Conquer Comes to the Rescue (again)
Algorithm
The Boyer-Moore Algorithm
Computing the majority vote on pen and paper
Analysis
Matchings in Bipartite Graphs and the Kőnig-Egerváry Theorem via LP Duality
We discuss how we can compute Maximum Matchings in bipartite graphs, and why these are equal to Minimum Vertex Covers.
Number Theory
The Celebrated Harmonic Numbers and How to Approximate Them
We discuss the famous harmonic sum and describe a simple way to approximate it.
Probability Theory
The Coupon Collector Problem
We discuss the well-known Coupon Collector problem, and provide two ways of computing the probability of winning.
Graph Theory
Turán’s Theorem for Graphs
Using the Probabilistic Method and the Cauchy-Schwarz inequality
Analysis
Mathematical Induction: The Domino Effect in Natural Numbers
We discuss the concept of mathematical induction on the natural numbers and give some examples.
Ramsey Theory
The Erdős–Szekeres Theorem
Monotonicity will prevail