**When and where:**
The class meets on Mondays, Wednesdays and Fridays from 10AM to 11AM in 4-149.

**Instructor:** Michel Goemans, room
E17-322. **Office hours: Thu ** 2:45PM-3:45PM.

**Teaching Assistant:** Francisco Unda, funda@mit.edu, office E18-301V. Office hour on Tue and Thu from 11:30-12:30 (E18-301V).

**This page:** http://math.mit.edu/~goemans/18310S15/18310.html

This course is an introduction to discrete applied mathematics. The topics presented are generally grouped into units covering between one and two weeks. These units include discrete probability, counting, sorting, RSA and modular arithmetic, data compression, linear programming, and error correcting codes. A tentative schedule will be posted. Lecture notes will be posted here. Note that unlike previous semesters, this is not a CI-M course.

**Grading:** The grade will be made up of problem
sets (30%), a 3-hour final exam during finals week (40%) and two 50-minute in-class quizzes (15% each). Your lowest problem set score
will not count. ** Quiz dates:** Mon March 9, 2015 and **Wed Apr 15, 2015.**

**Homework:**

- Problem set 1. Due at beginning of lecture on 2/13/2015.
- Problem set 2. Due at beginning of lecture on 2/25/2015. Update on 2/20/2015: only solve questions 1, 3 and 4.
- Problem set 3. Due at beginning of lecture on 3/6/2015. (No penalty if turned in on 3/9/2015 during the quiz.)
- Problem set 4. Due at beginning of lecture on 3/20/2015.
- Problem set 5. Due at beginning of lecture on 4/6/2015.
- Problem set 6. Due at beginning of lecture on 4/15/2015.
- Problem set 7 (last one). Due at beginning of lecture on 5/8/2015.

**Late policy:** It is possible to hand them in
late, with a 10% decrease in your grade, until 6PM the next day, in
which case you must email your assignment in PDF format to
goemans@math.mit.edu.

** Collaboration Policy.** Collaboration on homework is permitted, but you must write the solutions yourself;
no copying is allowed. At the top of your homework, list:

- The names of your collaborators; if you worked alone, state this.
- Any other sources you consulted, other than the course notes.

**Handouts:**

- Lecture notes on discrete probability
- Lecture notes on Chernoff bounds.
- Lecture notes on counting, coding and sampling (slightly updated on 2/16/2015)
- Lecture notes on the pigeonhole principle and the probabilistic method. (notes revised and updated on 2/20/2015)
- Lecture notes on generating functions. (notes slightly revised; section 8 needs revising.)
- Practice exam #1.
- Lecture notes on linear programming. (exercise 1.7 corrected on 3/17/2015)
- Lecture notes on maximum flows.
- Lecture notes on sorting.
- Lecture notes on Quicksort and randomized median finding.
- Lecture notes on sorting networks.
- Lecture notes on modular arithmetic and basic algebraic structures.
- Lecture notes on cryptography and RSA. Updated April 21st.
- Practice exam #2.
- Lecture notes on factoring.
- Lecture notes on the Discrete and Fast Fourier transform.
- Lecture notes on Shannon's noiseless coding. (slightly updated on 5/4/2015.)
- Lecture notes on Huffman coding.
- Lecture notes on Lempel-Ziv coding.
- Lecture notes on Shannon's noisy coding theoremg.
- Lecture notes on Hamming codes.
- Practice final.