Whoever links to these notes will show exquisite taste. Whoever copies
these notes will be prosecuted to the hilt.

Vašek Chvátal

- Analysis of algorithms:
- Proving correctness of programs (html).
- Adversary arguments and lower bounds (html).
- Average-case analysis of quicksort (pdf).
- The Knuth-Morris-Pratt string-matching algorithm (html).
- Lovász's reduction of COLOURABILITY to 3-COLOURABILITY (html).
- Lecture notes on the AKS sorting network (pdf).
- Harmonic numbers, natural logarithms, and the Euler-Mascheroni constant (html)
- Notes on the Master Theorem (pdf)

- Elementary number theory:
- A min-max theorem for the greatest common divisor (html).
- Taking square roots modulo a prime (html)
- Pratt's primality proofs (pdf).

- Programming:
- The inclusion-exclusion principle and Boole-Bonferroni inequalities (html)
- Notes on the Khachiyan-Kalantari algorithm (pdf).
- Notes on the maximal Lyapunov exponent of a time series (pdf)

Back to Vašek Chvátal's home page