CSC 310 — Information Theory, StG, Fall 2007
Announcements
Handouts
Contact
Timetable
Books
Grading
Lateness Policy
Important Dates
Links
Instructor Matei David
email: matei at cs
office: SF 4302-F
phone: 416-946-3924
Teaching Assistants Darius Braziunas
email: darius at cs
Ilya Sutskever
email: ilya at cs
Lecture Monday, Wednesday10 - 11amMP 118
Tutorial Friday 10 - 11am MP 118
Office Hours Wednesday11am - 12pmSF 4302-F
Textbook David MacKay. Information Theory, Inference, and Learning Algorithms (fifth printing). Cambridge University Press, 2006. This is the main book we will be following. We will be interested in chapters 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 47, and 50.

The book is available online here.
Reference Books G.A. Jones and J.M. Jones. Information and Coding Theory. Springer, 2000. Alternative textbook, contains the majority of subjects we will discuss in this course.
A. Drozdek. Elements of Data Compression. Brooks/Cole, 2002. This book is mainly concerned with data compression, touching on subjects such as compression of images and movies.
  • 3 Assignments worth 10% each = 30%. Assignments are to be done individually.
  • 1 Project that involves programming and running experiments, worth 20%. This may be done in groups of 1 or 2 students.
  • 2 Term Tests worth 25% each = 50%.
  • No final exam.
  • Assignments and the Project are due at 6pm on their respective due date, in the CSC 310 drop box in BA 2220.
  • Each student has 3 grace days, to be used as you see fit, common for the Assignments and the Project. These days end at 6pm. So, following a Monday due date, I will collect whatever is in the dropbox at 6pm on Monday, Tuesday, Wednesday and Thursday. The papers will be marked as having used 0, 1, 2 and 3 grace days, respectively.
  • If you have no grace days left and your assignment is late, it will not count.
  • For any kind of special arrangement, contact the instructor before that piece of work is due.
  • October 9th, Assignment 1 due.
  • October 19th, final exam timetable posted.
  • October 26th, Term Test 1.
  • November 4th, drop date.
  • November 5th, Assignment 2 due.
  • November 23rd, Project due.
  • December 3rd, Assignment 3 due.
  • December 7th, Term Test 2 and end of classes.
After classes The project was graded out of 100p, 70p for part 1 and 30p for part 2. Assignment 3 was graded out of 60p, 25p for question 1, 10p for question 2 and 25p for question 3. Test 2 was graded out of 50p instead of the stated 54p. Equivalently, the grades for test 2 were adjusted up linearly by a factor of 54/50. Maybe you will find the following numbers useful. Officially, they do not mean anything. [ numbers ]
Week 13 In the end, we decided that we won't need to hold an office hour to run the programs. Darius will give a tutorial on Wednesday in lecture time.

This week, I will hold office hours on Tuesday 3-4 and on Wednesday 11-12 and 3-4. Drop by my office if you have questions about the test or the assignments. The second test will be on Friday, 10-11 in our usual room, and it will cover everything we have done starting with and including lecture 14.
Week 12 Tomorrow, Friday, there will be a regular tutorial. Darius will have a look at the projects and decide if he needs to have you run the code. If there will be an office hour in the CDF lab for seeing how the code works, it will be Wednesday next week, during lecture time, 10-11. On Monday we will have the last lecture and Test 2 will be on Friday, 10-11.

Ilya will hold office hours for questions about A2 marking on Thursday, Nov 28th, 1-2pm in SF4302.

Here are some lecture summaries instead of notes: In lectures 21 and 22, we talked about low density parity check (LDPC) codes. We talked about the reasons Hamming codes are not quite useful, we defined LDPC codes, and we talked about how to perform decoding over the BEC (which was easier) then over the BSC. For reference, see sections 47.1 and lecture 20 from the 2006 course by prof. Sam Roweis. These contain all the details you need for Assignment 3. Decoding over the BSC is described in section 47.3, but we did not go into those kind of details. In lectures 23, 24 and 25 (next Monday included), we talked (and will finish talking) about Shannon's Noisy Channel Coding Theorem for the BEC and then for the BSC. My goal in presenting this proof is for you to understand the intuition behind the important steps overall, rather than the correctness of each individual step. For reference, see lecture 17 from the 2006 course. The proof can also found in chapter 10 in much greater detail than we saw in class.

Grace days for the Project. If you are doing the project in pairs, the maximum number of grace days you can use is the sum of you and your partner's grace days, or 3, whichever is less. So, if you have 2 grace days left and your partner also has 2, you may use up to 3. If you have 1 each, you may use up to 2. Please state on the submitted handout how the grace days should be charged. That is, if you each have 2 left and you use 3 grace days for the project, one of you will be left with 1 grace day. Please resolve these issues for yourselves. If you are doing the project by yourself, and only then, you may use 1 extra grace day for the project only, but again, up to a maximum of 3. Another way of putting it is to imagine you have a partner with 1 grace day.
Week 11 Another Clarification. If you load the matrix G into the variable G, and you load K bits in the vector x, when you do G'*x, Matlab will perform this operation over the integers. So, the result might contain entries which are not bits 0 or 1. You must take the result modulo 2 in order to simulate arithmetic in the field F2. This holds for all matrix manipulations, including the decoding part.

How to submit the project. The writeup, analysis and a printout of your code go to the drop box as usual. Submit your code electronically either using the command-line submit, or the web interface. The assignment name is "project".

Office hour. We will arrange for an office hour where you have to demonstrate the TA how the programs work on a few input files. The point of this is to convince him that it is your own work.

Clarification about the project. I have been getting questions about how to use a symbol with code 256 to represent the end of the file given that it is not a valid ASCII code. The answer: that character will not appear explicitly in any of the input or output files, so there is no need for it to be a valid ASCII code. You don't test for the end of the input file by checking if you read that special symbol, but using the usual end-of-file test from your favourite programming language (e.g. the return value of fread). The fact that you are using a source alphabet of size 257 will only be reflected in the number of subintervals created during your subdivisions.

I added a question to A3 about the LDPC decoding algorithm that we talked about on Wednesday.

Here is Assignment 3: [ assignment 3 ]. It is due on Monday, December 3rd. Check out the Lateness Policy for relevant information.
Week 10 Lecture notes for this week: [ lecture 19 ] [ lecture 20 ].

Part 2 of the project is now posted. You are encouraged to write the code for the second part in Matlab, as it can easily manipulate matrices. You need not write the two parts in the same programming language. Even though the description of part 2 is long, this part is much easier than part 1. Apart from dealing with input and output files, all the encoding and deciding operations consist of a few matrix multiplications. You need not complete part 1 to do part 2.

The project is due on Monday, November 26th. But you should finish it as soon as possible, as Assignment 3 is due only one week after that.
Week 9 Here are lecture notes up to date: [ lecture 14 ], [ lecture 15 ], [ lecture 16 ], [ lecture 17 ], [ lecture 18 ].

Here are details about the Course Project: [ project ]. As previously discussed, you have to implement Arithmetic coding and decoding with integer arithmetic. I will add a small channel coding question very soon.
Week 8 Here is Assignment 2: [ assignment 2 ]. It is due on Tuesday, November 13th. Check out the Lateness Policy for relevant information. You should be able to do all problems with material seen in lectures up to and including this Wednesday.
Week 7 Lecture notes for Friday last week: [ lecture 13 ].
Week 6 There is a problem with the grades for A1. The TA subtracted the marks you lost from 100, instead of 65. To get your real grade, subtract 35 and take the result out of 65. For example, if you got 89, that should be 54/65.

Here is the schedule for the following week. On Friday I will do a lecture and finish up the compression part of the course. On Monday next, you will have a tutorial with Ilya. On Wednesday next, we will do a lecture for the second part of the course. On Friday next, we have Test 1. The latter covers all of the material seen up to and including the lecture on this Friday.

Lecture notes for Wednesday: [ lecture 12 ]. These notes are very succint. The PPM and LZ77 algorithms are described with examples in the 2006 lectures 10 and 11. Section 6.4 describes the LZ78 (or LZW) scheme, which we will see on Friday.

Lecture notes for Monday: [ lecture 11 ].

Here are lecture notes on Arithmetic Coding: [ lecture 8 ] [ lecture 9 ] [ lecture 10 ]. For reference, in addition to section 6.2 in the book, check out the lecture notes for lectures 7 and 8 from the previous version of this course, taught by prof. Sam Roweis. To get there, follow the link from the Links section.
Week 4 Because there is no lecture the following Monday, I decided to hold another lecture this Friday. In class I said I'll lecture on next Friday, but I'd rather we finish the arithmetic coding for the next tutorial. If you have questions about assignment 1, go to Ilya's office hours on Thursday.

I will move my regular office hours from Wednesday 3-4 to Wednesday 11-12. This week, Ilya will hold extra office hours in case you have questions about A1 on Thursday, 1-2pm, in SF4302.

Lecture notes for Monday: [ lecture 7 ].
Week 3 Lecture notes for Wednesday: [ lecture 6 ].

Here are some lecture notes for all but the last lecture: [ week 1 ] [ lecture 3 ] [ lecture 4 ] [ lecture 5 ]. These lecture notes are not meant to be a substitute for lectures. There may be examples that we're doing in lecture that I'm not transcribing. Instead, my intention in posting them is to point out the key ideas that we talked about in lecture, so that you can reconstruct the arguments by yourself. In most places I point out the sections in the book that are relevant to the subject being discussed.

Here is Assignment 1: [ assignment 1 ]. It is due on Tuesday, October 9th. Check out the Lateness Policy for relevant information. You should be able to do problems 1, 3 and part of 2 with material presented up to and including the lecture on Wednesday. For problem 4, read section 4.1 in the book. For the second part of problem 2, you will need material that we will talk about in lecture next Monday.
Week 2 I posted information about the grading scheme, the lateness policy, and the important dates.
Week 1 There will be no tutorial this week.

If you do not meet the prerequisites for this course, you will be automatically removed. To avoid this, talk to the instructor about getting a waiver.