These scanty notes are meant only to supplement textbooks, not to
replace them: the annotations and explanations are sparse and
references are often missing.
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:
- Programming:
- C implementation of arithmetic with arbitrarily large integers
(html):
a couple of examples of code using the GMP library.
- Timing programs with getrusage (html)
- 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)