Haris Angelidakis – Cantor's Archive

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

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