18.091 Assignments

Homework 1: Due Tuesday, Sept. 12

Read the paper "The Best Card Trick," by Michael Kleber, and write a paragraph or so on whether you thought it was a good piece of mathematical writing. If so, what techniques do you think were particularly effective. If not, how do you think it could have been improved. This paper appeared in the Mathematical Intelligencer, which I think is a good source for well-written articles on mathematics. This magazine is intended for mathematicians in general.

While there is no requirement to figure out what the Birkhoff-von Neumann or the Hall Marriage theorem are in order to do this assignment, you can answer the question of how well they are explained in the text, and whether they should have been explained more thoroughly. I taught Hall's theorem in 18.310 last year, and Hall's theorem (together with several of its numerous applications) would be a reasonable topic for the 18.310 term paper.

Homework 2: Due Tuesday, Sept. 19

Due September 19: Hand in a one- or two- page exposition of an o(n²) sorting routine. That is, a sorting routine which is asymptotically faster than c n² for any c. (The only one I can think of offhand that is o(n²) but not O(n log n) is shellsort.) It may be one of the O(n log n) ones covered in class, i.e. mergesort, quicksort or heapsort, or it may be a different one. You should contain a detailed description of how the algorithm works, an estimate of the number of comparison, and a short discussion of the advantages and/or disadvantages of this sorting method. (A rigorous proof of this estimate is not necessary, but some form of argument is needed.)

Revisions due Thursday, Sept. 28

Assignment 3: Due Thursday, Sept. 28/ Tuesday, Oct. 2

Give a 10 minute blackboard presentation. Pick an 18.310 homework problem. Present it to the class at the chalkboard, assuming that the class knows what a typical 18.310 student knows. Rather than just giving the solution, you should give a brief introduction to the problem and try to motivate the solution, if required.

A random drawing of names gave the order
Rebecca Idell
Kate Hoff
Eric Liu
Jaime Quinonez
Samson Zhou
Qifong Liu
Eleanor Lin

Assignment 4: Due Thursday, Oct. 12

Carefully write up a proof of one of the following theorems. Make sure you state the theorem clearly. It should be aimed for the level of an 18.310 student.

a. There is a non-adaptive weighing scheme that uses k weighings to find a good coin if you have (3^k−1)/2 coins, one of which is bad.

b. Prove that the Huffman algorithm produces the optimal binary code for a given set of letter probabilities.

c. Prove that the Hamming code can encode 2^k−k−1 bits using 2^k−1 bits and can correct one error.

d. Prove that the expected number of comparisons used by Quicksort is to leading order 2 n log_e n. You will have to do some research for this one. There is a very nice proof that uses indicator variables, which you should be able to find by searching the internet.

e. Prove the Shannon source coding theorem. Make sure you state the theorem precisely.

f. Prove information-theoretic bound for channel coding. That is, prove the information theoretic upper bound on how much information can be sent through a noisy channel.

Assignment 5: Due Tuesday, Oct. 31

Write a three-page paper explaining some topic which is being or has been covered in 18.310.

Assignment 6: Due Thursday, Nov. 2

Write a paragraph about the topic of your term paper. Carefully write up a proof of one of the following theorems. Make sure you state the theorem clearly. It should be aimed for the level of an 18.310 student.