| SES # | TOPICS | LECTURE NOTES | PREVIOUS TERMS |
|---|---|---|---|
| L1 | Non-adaptive weighing | (PDF) | (PDF) 2006 notes (PDF) |
| L2 | Sorting | (PDF) | (PDF) |
| L3 | Finding the median | (PDF) Supplement (PDF) | (PDF) |
| L4 | Non-adaptive sorting: Batcher's algorithm | (PDF) | (PDF) |
| L5 | Shannon source coding: coding for efficiency | (PDF) | (PDF) |
| L6 | Huffman and Hu-Tucker algorithms; finding efficient compression | 6.1 (PDF) 6.2 (PDF) Hu-Tucker (PDF) Lempel-Ziv (PDF) | (PDF) |
| L7 | Theory of probability | (PDF) Supplement (PDF) | (PDF) |
| L8 | Coding for error correction: the Shannon bound | (PDF) | (PDF) |
| L9 | Matrix hamming codes | (PDF) | (PDF) |
| L10 | Polynomial codes | (PDF) Supplement (PDF) | (PDF) |
| L11 | BCH codes: constructing them and finding the syndrome of a message | (PDF) Supplement (PDF) | (PDF) |
| L12 | Correcting errors in BCH codes | (PDF) | (PDF) |
| L13 | Properties and generalizations of our BCH codes | (PDF) | (PDF) |
| L14 | Coding for secrecy | (PDF) Euclidean algorithm (PDF) | (PDF) |
| L15 | Secret coding 2 | (PDF) | (PDF) |
| L16 | Factoring numbers | (PDF) | (PDF) |
| L17 | Quadratic sieve and elliptic curves | (PDF) | (PDF) |
| L18 | Some graph theory | (PDF) Kuratowski's theorem (PDF) Kuratowski's planarity (PDF) | (PDF) |
| L19 | Planarity and coloring; matching problems | 19.1 (PDF) 19.2 (PDF) | (PDF) |
| L20 | Counting trees | (PDF) Supplement (PDF) | (PDF) |
| L21 | Symmetries | (PDF) | (PDF) |
| L22 | Counting patterns; generating functions | 22.1 (PDF) 22.2 (PDF) | (PDF) |
| L23 | The finite Fourier transform | (PDF) | (PDF) |
| L24 | FFT and multiplication of numbers | (PDF) FFT (PDF) Supplement (PDF) | (PDF) |
| L25 | Sequential choice | (PDF) | |
| L26-27 | Linear programming | (PDF) | (PDF) (PDF) |
| L28 | Duality in linear programming | (PDF) Duality (PDF) Supplement (PDF) | (PDF) |
| L29 | Matching | (PDF) Parenthesis (PDF) | |
| L30 | Strassen's fast multiplication of matrices, algorithm and spreadsheet matrix multiplications | (PDF) | (PDF) |