18.310 - Fall 2004


Lecturer: Professor Peter Shor


Teaching Assistants:

Sergiy Sidenko

Uri Laserson

I am going to be more or less following Prof. Kleitman's lecture notes for the course this year. You can find the lecture notes from Prof. Kleitman's course in 2004 on the web. I will be going over much the same material, and for the lectures where I don't use his notes, I'll put up some course notes. There will be weekly homework and a term paper.

Here is a tentative syllabus.

Syllabus 2005 (tentative)

Reminder. Second exam, in-class 11/21.

About the exam. You can bring in cheat sheets (four pages, either four one-sided sheets or two pages, both back and front). It will cover everything gone over since the midterm material.
Some sample questions are now posted here. The solutions that I've written up so far are posted here. The solutions to problem set 8 (at least, to problems 1 and 2) are posted here. The spreadsheet solution for (problem 2) is (in three variations) here. Finally, there is NO HOMEWORK due this week. The next (and last) homework will be due on December 2, and will cover linear programming, which I'll be talking about for another week or so.


Here are some guidelines for the term paper: I would like it to be at least 8 pages. There is also (as Prof. Kleitman did) a programming option for the project, which involve writing a program rather than doing a term paper. People choosing the programming option also have to turn in a paper of at least two or three pages explaining what the program does and how it does it. (And if it's only two pages, I would expect the program to be well documented.)

For those of you taking 18.091, you may use the same term paper for both classes, but you will need to follow the requirements for communications intensive courses: for example, the term paper must be at least 10 pages and go through several rounds of revision.

And here is Prof. Kleitman's list of sample topics for the term paper. Sample Topics for Term Paper

Homework Assignments:

The rules for homework are the standard MIT ones. Collaboration is allowed, but you have to write up your own solutions, and you have to write down the names of anybody you collaborated with. The homework will be due Fridays; you can hand it in after class, of you can drop it outside my office before 4 pm.

Programs written for the homework should be emailed to me (shor@math.mit.edu) with the words "pset solution" in the subject.

Note that in Homework 1, I mixed up rows and columns in the hint for problem 3.2. I hope that didn't confuse anybody too much.

1.   Homework 1

2.   Homework 2

3.   Homework 3

4.   Homework 4

Hint for problem 1c. In problem 1b, you showed that in the Hu-Tucker algorithm, we create nodes in order of increasing frequency. This fact was used in the proof that the Hu-Tucker algorithm works. In particular, we used the fact that if we created a node a with the edges crossing over another node b, then freq(a) is larger than freq(b). So figure out a scenario where freq(a) and freq(b) are equal, and then use node a next rather than node b. If you do this right, you will get a counterexample.

5.   Homework 5

3.   Solutions for the test are here.

6.   Homework 6

7.   Homework 7 and here are the hints for homework 7. I meant to put them up earlier, but I completely forgot about it. Many apologies

8.   Homework 8 is out. I'm sorry that I got it out so late. It's due Monday, November 14.

This is the last homework. It is due Monday, December 5.

9.    Homework 9 is out. You also need This spreadsheet to do it.

I have had some complaints about people not being able to load this spreadsheet. Many thanks to Andrew Spann, who found a solution posted here. And if that doesn't work, you can do Problem 1 from this html version of the spreadsheet, here. and Problem 2 using some other linear programming package (Maple, Mathematica, and MATLAB all have adequate ones). The comments look a little spacey in html, but it should be comprehensible.

For problem number 2, I never intended you to do all the pivoting by hand ... if you do that, it's a really tedious task. You can use my spreadsheet. I did made a minor mistake in this spreadsheet which is now fixed, but might affect your work on problem 2 (not problem 1). To do problem 2 on the spreadsheet, you may have to add another column to the tableaus, but this is easy to do using copy and paste (and make sure row 1 is correct).

Course Notes:

I am posting links to Prof. Kleitman's course notes, and to the OCW notes lecture notes for 18.310 (taken in 2004). If they don't work, please email me, and I'll fix it.
I'll write course notes for any lectures where I deviate from his syllabus, although it might take me several days after the lecture. You can find all Kleitman's notes on his course webpage. The OCW Lecture notes are Here

1.   Non-Adaptive Weighing: Kleitman's notes and OCW notes

2.   Sorting: Kleitman's notes and OCW notes
I went over the algorithms in a different order, and omitted tournament sort from my lecture. We will complete heapsort on Monday, the 12th.

3.   Finding the Median: Kleitman's notes and OCW notes
I altered Kleitman's notes to give what I think is a somewhat better explanation.

4.   Non-Adaptive Sorting: Batcher's Algorithm Kleitman's notes and OCW notes
I added a picture to the explanation in Kleitman's notes here.

5.   Theory of Probability: Kleitman's notes and OCW notes

6.   Shannon Source Coding: Kleitman's notes and OCW notes

7.   Huffman and Hu-Tucker Coding: Kleitman's notes and OCW notes
I have also altered Kleitman's notes on the Hu-Tucker algorithm to make them match my explanation in the lecture, which differs from Kleitman's explanation (even though they lead to the same Hu-Tucker tree). I eventually plan to put part of the proof that the Hu-Tucker algorithm works in these notes. My notes on the Hu-Tucker algorithm.

8.   Lempel Ziv Coding. Prof. Kleitman didn't do this topic, so I don't have his notes. I have found a set of notes online at Here or Here in the smaller type paper-saving version These notes are at a higher level than I used in covering the subject. I've written my own notes for this lecture.

9. The Shannon Bound:   Kleitman's notes and OCW notes

10.Matrix Hamming Codes   Kleitman's notes and OCW notes

11.Polynomial Codes and some lore about Polynomials Kleitman's notes and OCW notes

12. BCH Codes: Constructing them and finding the Syndrome of a Message: Kleitman's notes and OCW notes

13. Correcting Errors in BCH codes  Kleitman's notes and OCW notes

13. Properties and Generalizations of our BCH Codes   Kleitman's notes and OCW notes

For the Wednesday 19th, lecture, I was planning on just doing the basic definitions from graph theory, and Kuratowski's theorem from the lecture notes. While preparing for the class, I realized that not only is the proof of Kuratowski's theorem in the OCW lecture notes wrong, but I think it's wrong in more than one way. It's possible to fix it (that is, there is a proof that goes along the same lines, and uses the construction of the cycle and the bridges), but it's not easy to do it from the notes. The notes on Prof. Kleitman's web page seem to be pretty much right, as far as they go, but they are so vague that you can't figure out a complete proof of Kuratowski's theorem from them. I will talk about a special case of Kuratowski's theorem that can be proved using the techniques from the lecture notes, and wave my hands about how you prove the general theorem using the same techniques. Anyway, here are the lecture notes with the part we're not doing in red. Here are Kleitman's notes and My notes.

15. Planarity and Coloring   Kleitman's notes and OCW notes

16. Depth first search and breadth first search. I realize I don't have time to write notes for both this and the generating function lectures. Here are some course notes I found on-line for depth-first-search and biconnected components. Breadth first search and depth first search
and depth first search for biconnected components

17 and 18. Generating functions. Here are my notes My notes. They're still not complete, but nearly everything is there

Here are my lecture notes for the FFT. and here are the Prof. Kleitman's 19. The Finite Fourier Transformand OCW notes

20. FFT and Multiplication of Numbers

22. Prof. Kleitman's lecture notes on Linear Programming. Note that these notes define the dual of a linear program incorrectly. The OCW lecture notes on linear programming are Part 1 , Part 2 , and Part 3 (Duality) . They seem to get the duality theorem wrong in some places, and right in others, and are somewhat confusing on the topic of duality. Finally, here are my notes Duality .

Here is Prof. Kleitman's introduction for the course. Introduction