18.310 Syllabus 2002 (tentative)

Date Topic

1 9/4/2002 Introduction. Weighing PS1 assigned

2 9/6/2002 Sorting Methods

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

4 9/11/2002 Batchers' Algorithm

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

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

7 9/18/2002 Probability Review

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

9 9/25/2002 Matrix Codes

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

11 9/30/2002 Correcting Several Errors PS5 assigned

12 10/2/2002 BCH Codes

13 10/4/2002 Locating errors using BCH codes

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

15 10/9/2002 Some counting problems Counting trees

16 10/11/2002 First Examination given

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

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

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

20 10/23 More on Same; Multiplying Matrices fast

21 10/25 More Generating Functions

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

23 10/30 RSA Codes: Finding large primes

24 11/1 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/4 Quadratic Sieve Factoring

26 11/6 Elliptic Curve Factoring PS9 due PS10 out

27 11/8 Operations Research: Linear Programming

28 11/13 The simplex algorithm

29 11/15 Duality

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

31 11/20 Second Examination

32 11/22 The Ellipsoid Algorithm and others

33 11/25 How good is the simplex algorithm?

34 11/27 Some Game Theory

35 12/2 Statistical Mutterings

36 12/4 Applications to Biology

37 12/6 Complexity

paper due as of this day

38 12/9 More Games

39 12/11 Famous false proofs

12/24 last date papers accepted