18.310 Syllabus 2005 (revised)

         Date               Topic

1     9/7/2005          Introduction. Weighing                       

2     9/09/2005        Sorting Methods                          

3     9/12/2005        Finding Medians                                 

4     9/14/2005        Batchers' Algorithm

5     9/16/2005        Probability Theory                             

6     9/21/2005        More Probability Theory             

7     9/23/2005        Shannon's Source Coding Theory

8     9/26/2005        Huffman and Hu Tucker codes                  

9     9/28/2005        Lempel-Ziv Coding

10   9/30/2005        Shannon's Channel Coding Theorem         

11   10/3/2005        Hamming Codes                       

12   10/5/2005        Polynomial Codes

13   10/7/2005        BCH Codes

14   10/12/2005        Locating Errors using BCH Codes                                ’

15   10/14/2005       Review for Exam

16   10/17/2005      First Examination given

17   10/19/2005      Some graph theory   

18   10/21/2005      Planarity

19   10/24/2005 Depth-First Search and Breadth-First Search                             

20   10/26/2005              Generating Functions

21   11/28/2005              More Generating Functions

22   10/31/2005               Fourier Transforms, Fast Fourier Transform

23   11/02/2005              FFT and Multiplying Numbers

24   11/04/2005               Linear Programming

start thinking about a paper topic; try to have one in one week

25   11/07/2005               The Simplex Algorithm  

26   11/09/2005                Duality                          

27   11/14/2005                Duality

28   11/16/2005              Applications of LP: Max Cut/Min Flow    

29   11/18/2005                Review for exam.    

30   11/21/2005                Second Examination       

31   11/23/2005              Applications of LP: Game Theory  

32   11/28/2005               More Game Theory

33   11/30/2005               The ellipsoid algorithm and others

34   12/02/2005               Secret Codes: RSA

35   12/05/2005                More on RSA Codes:

36   12/07/2005                Breaking RSA Codes: Factoring and the Quadratic Sieve Algorithm

37  12/09/2005                Breaking RSA Codes: Quantum Factoring Algorithm

paper due 12/12/2005

38  12/12/2005                 Discrete logarithms, the Diffie-Hellman Cryptosystem and others.         

39  12/14/2005                 To Be Announced