We will be using a blog for the
course in lieu of a course newsgroup. All announcements will be made on the blog.
If you are attending the course,
you must check the blog regularly (and consider subscribing to the
RSS feed).
This will give an overview of the topics we will cover in the class. Comments are welcome.
Course Pre-requisites
There is no specific course pre-requisite for this course. However, some "mathematical maturity" will be essential. In particular, comfort with basics of linear algebra (vector spaces, basis, dual spaces); finite fields, field extensions and polynomials over finite fields; elementary probability; analysis of algorithms; and (some exposure to) computational complexity will be useful.
Some of these topics (for example finite fields) can be learned on a need to know
basis as the course progresses. Email the instructor if you have any questions
on the pre-requisites.
Reference material
We will not follow any particular textbook.
The closest resource is the excellent set of lecture notes for
Madhu Sudan's coding theory
course at MIT: Notes from 2001, 2002 and 2004.
The basic material on
codes that we will discuss in initial lectures can be found in one of many
textbooks (some of the standard ones are listed below), but the recent algorithmic
developments and applications in computer science
are not covered in any of these:
Introduction to Coding Theory, by J. H. van Lint, GTM 86.
The Theory of Error Correcting Codes, by F. J. MacWilliams and N. J. A. Sloane, North-Holland, Amsterdam.
Algebraic codes for data transmission. by Richard E. Blahut.
Though we won't cover much information theory in this course, if your curiosity is aroused on aspects such as entropy, mutual information, capacity theorems, source coding, etc., there is the classic information theory text
Elements of Information Theory, Thomas M. Cover and Joy A. Thomas,
Wiley Series in Telecommunications, 1991.
Workload
The workload will be moderate: there will be no exams. The following
will be the major components:
Scribing lecture notes. Depending on the strength of the class a student might
have to scribe 3-4 lectures. I will typically ask for a volunteer at the
beginning of the class.
Homeworks. About 2 of them.
Survey report. Every student is expected to review literature on
some aspect of coding theory and submit a report by the end of the semester.
The topic can be some aspect that could not be covered in the class in detail
or could be a topic that was not covered at all in the class. Working on an
open research problem is welcome but not mandatory.
A list of topics (and more details) will be posted later on.
Grading Policy
Here is a rough split of grades:
Scribing notes (30-40%). The scribed notes will be graded on the timeliness
of completion as well as the quality of the writeup.
Homeworks (30-15%). Collaboration in groups of size at most three is
allowed (and encouraged). However, every student is expected to do their
own writeups and clearly state the names of their collaborators. More details
will be available when the homeworks are handed out.
Project reports (40-45%). The grade will depend on the clarity/quality
of presentation as well as the depth of material covered.
