Lecturer: Professor Peter Shor
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
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 (firstname.lastname@example.org) 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
6. Homework 6
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.
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).
7. Huffman and Hu-Tucker Coding:
Kleitman's notes and
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.
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.
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.
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
22. Prof. Kleitman's lecture notes on
Note that these notes define the dual of a linear program incorrectly.
The OCW lecture notes on linear programming are
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
Here is Prof. Kleitman's introduction for the course. Introduction