Skip to content

Appearance

Sidebar Navigation

Math Toolbox

Introduction to the Course

Logic

Proposition

Quantifiers

Basic proof techniques

Direct proof

Contraposition

Contradiction

Case analysis

Proof by induction

Finding the right hypothesis

Strong induction

Proving things about algorithms

Recursive binary search

Iterative binary search

Loop invariants

Graphs and Algorithms

Introduction

Graph classes and isomorphisms

Graph classes

Isomorphisms

Some structured graphs

Trees

Planar graphs

Directed graphs

Eulerian digraphs

Tournaments

Numbers and Algorithms

Modular arithmetic and Euclid

Number operations

Exponentiation

Inverse

Cryptography

RSA

Fermat's little theorem

Prime numbers and finger printing

Asymptotic estimates

Estimates on primes and fingerprinting

Counting: From Finite to Infinite and Beyond

Combinatorial counting

Sampling with replacement

Sampling without replacement

Permutations

Binomial coefficients

Partition

Binomial theorem

Application: Analyzing recursion

Combinatorial estimates

Factorial estimates

Binomial coefficients

Countability and Computability

Countable sets

Diagonalization

Computability

Discrete Probability

Probability spaces

Coin tossing

Balls and bins

Random graphs: The Erdös-Rényi model

Conditional probabilities and so on

Amelia's exam

COVID treatments

Independence and correlations

The case of two events

Multiple events

Random graphs, revisited

Random variables

Expectation

Balls and bins

Fixed points of permutation

Professor's misery

CS application: Large cuts

Balls and bins

Algebra in Computer Science

Univariate polynomials

Proof of Theorem 44 (Interpolation)

Proof of Theorem 43 (Roots of polynomials)

Finite fields

Application: Secret sharing

Application: Error-correcting codes

Multivariate polynomials

Matrix multiplication testing

The Schwartz-Zippel Lemma

Perfect matching detection

Proof of Theorem 48 (Schwartz-Zippel Lemma)

On this page

Math Toolbox ->
Introduction to the Course ->
Proving things about algorithms

Proving things about algorithms

📄️ Recursive binary searchSingle Page

📄️ Iterative binary searchSingle Page

📄️ Loop invariantsSingle Page

Pager

Previous pageStrong induction

Next pageRecursive binary search

Toolbox by Hilmy Abiyyu Asad from the Noun Project. © 2026 Me. Built with VitePress.