**Lecturer: **

- Room: 2-369
- Phone: 253-4362
- Email:
`shor@math.mit.edu` - Office Hours:

Monday, 3:00 - 3:30.

I will be having special additional office hours from 1:30 to 2:30 today, Monday Nov. 14

Wednesday, 1:30 - 3:00.

Thursday, 1:00 pm - 2:30 pm.

**Teaching Assistants:**

*Sergiy Sidenko*

- Room: 2-090
- Email: sidenko@math.mit.edu
- Office Hours: No more office hours

*Uri Laserson*

- Room: 2-091
- Email: laserson@mit.edu
- Office Hours: No more office hours

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.

**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.

** TERM PAPER**

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