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 or subscribe to receive email notifications for new posts.).
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. Instead, we will use lecture notes
from the previous fall 2007 and spring 2009 offerings of the course.
Note: Unfortunately, not all the lecture notes are
polished (i.e. those marked as draft): I plan to polish them before the
relevant lecture this semester.
Another good resource is the excellent set of lecture notes for
Madhu Sudan's coding theory
course at MIT: Notes from 2001, 2002, 2004 and 2008. You might also want to check out the
notes from Venkat Guruswami's coding theory course.
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 you are
interested to know more on topics such as entropy, 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 notes. A few lectures will cover topics that were not
covered in the last offering: these lectures will need to be scribed.
I don't expect this load to be more than one lecture/student. I will typically ask for a volunteer at the
beginning of the class.
Proof-reading notes. For lectures that have already been covered before,
I will ask a volunteer to go over the existing lecture notes and email me
any comments that they might have (e.g. typos, something that needs better
explanantion etc.). Depending on the number of students, each student might have
to volunteer for 6-7 lectures. However, each of them should not be time consuming
as all of these notes would have been proof-read by me at least once.
Updating Wikipedia. Every student will pick a coding theory topic
that is either absent or not well documented on Wikipedia and write/edit the corresponding entry.
You will have the opportunity
to work on initial versions of the entry on an in-house wiki page
before the entries are posted on Wikipedia (you'll need
to get my OK before you post your entry on Wikipedia). See the syllabus for the various
deadlines.
Homeworks. Either one long or roughly 3 short ones.
Grading Policy
Here is a rough split of grades:
Scribing/Proof-reading notes (30-40%). The scribed notes
entries will be graded on
and timeliness of completion.
Homeworks (40-25%). 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.
Updating Wikipedia (30-35%). The grade will depend on the clarity/quality
of the writeup. For more details see the syllabus.
The material in this webpage is supported in part by the National Science Foundation under CAREER grant CCF-0844796. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
