18.310 Syllabus 2004 (tentative)

         Date               Topic

1     9/8/2002          Introduction. Weighing                       PS1 assigned

2     9/10/2002        Sorting Methods                          

3     9/13/2002        Finding Medians                                 PS2 assigned PS1 due

4     9/15/2002        Batchers' Algorithm

5     9/17/2002        Shannon's Theorem                            PS2 due

6     9/20/2002        Huffman and Hu Tucker codes            PS3 assigned

7     9/22/2002        Probability Review

8     9/24/2002        Shannon's Second Theorem                 PS3 due PS4 assigned

9     9/27/2002        Matrix Codes

10   9/29/2002        Polynomial codes, Hamming codes        PS4 due

11   10/1/2002        Correcting Several Errors                      PS5 assigned

12   10/4/2002        BCH Codes

13   10/6/2002        Locating errors using BCH codes

14   10/8/2002        Some combinatorics                              PS5 due Review Q’s out

15   10/13/2002      Some counting problems Counting trees

16   10/15/2002      First Examination given

17   10/18/2002      Counting Problems: inclusion exclusion   PS6 assigned

18   10/20/2002      Generating functions Fourier Transform; Finite FT

19   10/22               FFT and Multiplying Numbers              PS6 due, PS7 assigned

20   10/25              More on Same; Multiplying Matrices fast

21   10/27              More Generating Functions

22   10/29              Secret Codes; RSA codes: how to construct them PS7due PS8 out

23   11/01              RSA Codes: Finding large primes

24   11/03              Breaking RSA codes: factoring numbers PS8 due PS 9 out

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

25   11/05               Quadratic Sieve Factoring 

26   11/08               Elliptic Curve Factoring                        PS9 due  PS10 out

27   11/10               Operations Research: Linear Programming

28   11/12               The simplex algorithm

29   11/15               Duality 

30   11/17               How Good is the simplex algorithm       PS10 due

31   11/19               Second Examination

32   11/22               The Ellipsoid Algorithm and others

33   11/24               How good is the simplex algorithm?

34   11/29               Some Game Theory

35   12/01               Statistical Mutterings

36   12/03               Applications to Biology

37  12/06                Complexity

paper due as of this day

38  12/08                 More Games and False Proofs        

12/24  last date papers accepted