CS 798: Kolmogorov complexity and its applications
Fall 2007

Home | Fun readings

Ming Li DC 3355, x4659 mli@uwaterloo.ca
Course time:Mondays 4:30--7:00pm DC 3313
Office hours:Mondays 1:30-3:30pm or just drop by my office any time.
Textbook:Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 2nd edition, Springer, 1997

The course material will be mainly from our textbook and papers that will be provided at this website. The students will do a small research project at the end of the term, and present them in class.

Note that this course is not a bioinformatics course. It is a general course on Kolmogorov complexity and many of its applications. Kolmogorov complexity is a modern theory of information and randomness. The goal of this course is to teach the students the basic concepts of Kolmogorov complexity and how to use this tool in their own research.

Topics include: plain Kolmogorov complexity, randomness, prefix Kolmogorov complexity, incompressibility method, information distance, applications in various fields ranging from average-case analysis of algorithms to bioinformatics and from document comparison to internet search. We will not be able to cover the complete textbook, rather we will focus more on recent developments and especially on applications of Kolmogorov complexity.

Marking Scheme: Each student is expected to do three homeworks and a final project, which can be either theoretical or programming, and present the project in class. Three homeworks 20% each, final project and presentatoin 35%, 5% class attendance (including guest lectures and student presentations) and participation in discussions.

Course announcements and lecture notes will appear on this page. You are responsible for reading it (and downloading the lecture notes before classes) regularly.


Possible project topics:


Note: The lecture notes are constantly being improved, so it is a good idea to download the most recent version before class.


Maintained by Ming Li