Lecture notes

These are sometimes quite raw versions.  Do not automatically believe everything that you find there, and please let me know if you discover mistakes, things that are not clear, and so on. I will also be glad to hear about experience with these lecture notes in teaching or as a study material.

For electronic correspondence, please use my surname at kam.mff.cuni.cz.

The probabilistic method (with Jan Vondrak)

Lecture notes to a course on the probabilistic, mostly follows the Alon-Spencer book, includes a review of notions from probability theory. The above file needs 46 pages to print, having two small pages per A4 printer page, and here is a more usual A4 format (ca. 70 pages).

Basis pursuit and the Johnson--Lindenstrauss lemma

A 9-page note on computing sparse solutions of underdetermined linear systems by linear programming ("basis pursuit"), with a more or less self-contained exposition of a result of Donoho, Candes and Tao, and Rudelson and Vershynin, proved using a recent observation due to Baraniuk et al. Extends a section from my book with Bernd G"artner Understanding and using linear programming.

Older lecture notes on incremental geometric algorithms and some algorithms for  planar arrangements

(notes from computational geometry, which I currently do not plan to update or extend anymore)

Jiri Matousek's home page