Algorithmic Information Theory
For the basics of the course, we will follow sections 1, 2, 3
and 5 from in the notes from the older
offerings. We will have the following topics in the second half
of the course.
 Martingales over binary sequences
 The Ziv Lempel Algorithm (LZ78)
 Optimality properties of the Ziv Lempel Algorithm
 The Law of Large Numbers  Weak, Strong
 Normal numbers
Meeting Times
The meeting times are Monday and Wednesday: 5:10 to 6:25 pm
over the Zoom link which will be communicated over the course
id. The class will be in a synchronous mode. But the video will be
recorded and uploaded for later viewing.
Grading policy
The course will have 2 assignments and 2 exams, with the
following weightage:
Homeworks: 15 percent each
Midsem : 30 percent
Endsem : 40 percent
The TA is Prateek Vishnoi. His email id is pratvish.
Additional Notes
In addition to the Notes of Section 4 which deal with
martingales, the following gives an alternative approach to the
theory of constructive
martingales: Notes on Constructive
Martingales
Special Topics
 Normal Numbers and finitestate compression
 The LempelZiv algorithm, universal (over finitestate)
compression.
 Applications of expander graphs and extractors to Algorithmic
Information Theory.
Additional References

Short Lists with Short Programs in Short Time  A Short Proof
by Marius Zimand.
 Fortune's Formula: The Untold Story of the Scientific Betting
System That Beat the Casinos and Wall Street, by William
Poundstone
Homeworks
 Homework 1 due the Friday before
Midsem week.
 Homework 2 due April 17 2019.