18.424 Seminar in Information Theory

When and where: The class meets on MWF from 3:00 to 4:00 in room 2-136.

Instructor: Peter Shor, room 2-369.

Office hours: I will be available by appointment to help prepare the presentations if need be.
I will also hold scheduled office hours the days before the homework is due. The next will be Thursday, April 10, from 2:30 to 3:30. and Friday, April 11, before class (1:00-3:00).

Homework

Homework 1: do problems 2.6, 2.9, 2.10, 2.14, and 2.25 in Cover and Thomas. Due Tuesday, Feb. 20.

Homework 2: do problems 5.5, 5.19, 5.25, 5.27, 5.30 and 5.32 in Cover and Thomas. Due Monday, March 5.

Homework 3: is posted. Due Monday, March 19

Homework 4: Write a brief paragraph about the subject of your term paper. Do problems 7.24, 11.5, 11.15a, 13.5, 13.6 Due Friday, April 13.

This is a new undergraduate seminar in information theory. It carries CIM credit for the math department. Enrollment is limited by the department.

The textbook is Elements of Information Theory, 2nd edition, by Cover and Thomas. The good news about this textbook is that the 2nd edition just came out, and has numerous mistakes fixed, many more exercises, and additional material. It is available in the book store. The bad news is because it's new, you may not be able to get a 2nd hand copy of the 2nd edition cheaply. We may do some material in MacKay's book, which is available online as well as in hardcopy.

This is a seminar class, so you will actually be teaching it to yourselves. Everybody will have to give three periods worth of lectures.

I think Information Theory is a fairly good topic for a seminar class, since (except for certain explicit constructions of error correcting codes) it is fairly broad. There is a small amount of material that underlies all of it. These are the concepts of information and entropy, and the properties of these quantities. There are many different possible branches of information theory that build on this, but which are relatively independent. Everybody is thus going to have to learn the underlying material fairly well. So I feel that I should probably start off by giving three lectures about properties of information, the equipartition property, and Shannon's source coding theorem. I will also give approximately four homework assignments during the term.

We will then start off by having students give lectures on various methods of source coding. After the source coding section, we'll do the channel coding theorem, possibly do some methods for channel coding, and we will also do certain other applications of information theory. These might be the rate-distortion theory, information capacity of networks, or how information theory relates to probabilistic inference or to gambling. Exactly what we do will depend on the students' interests. I expect around half of the topics will be out of the textbook.

Students will be expected to present two and a half class periods during the term. You will also be expected to write a 10-page paper on some topic related to information theory.

Dates You should come up with a topic for your term paper around April 2. The first draft of the paper will be due on April 25.

Grading policy. Your grade will be based on your participation (i.e. your own presentations, and also your participation during other presentations), the homework, and your project, in the ratio 50% participation, 25% homework, and 25% project. You are expected to attend all lectures (if not excused).

The prerequisites are having some courses on linear algebra and probability theory.

Here is a partial list of possible topics.

Schedule