18.310 - Fall 2004

 

Lecturer: Professor Daniel Kleitman

 

Teaching Assistants:

To be assigned

To be announced

 

Introduction 2006

Introduction

Syllabus 2004 (tentative)

Assignment 1 2004

Assignment 2 2004

Assignment 3 2004

Assignment 4 2004

Assignment 5 2004

Assignment 6 2004

Assignment 7 2004

Assignment 8 2004

Assignment 9 2004

Assignment 10 2004

Review Questions for Exam 1

Exam 1: Numbers 2, 5, 8, 11, 15 from the review question list.

Exam 2

Assignment 1 2002

 

1.   Non-Adaptive Weighing

2.   Sorting

3.   Finding the Median

4.   Non-Adaptive Sorting: Batcher's Algorithm

5.   Coding for Efficiency

6.   Finding Efficient Compressions; Huffman and Hu-Tucker Algorithms

7.   The Theory of Probability

8.   Coding for Error Correction: the Shannon Bound

9.   Matrix Hamming Codes

10. Polynomial Codes and some lore about Polynomials

11. BCH† Codes: Constructing them and finding the Syndrome of a Message

12. Correcting Errors in BCH Codes

13. Properties and Generalizations of our BCH Codes

14. Some Graph Theory

15. Planarity and Coloring

16. Counting Trees

17. Symmetries

18. Counting Patterns

19. Coding For Secrecy

20. Secret Coding 2

21. Factoring Numbers

22. The Quadratic Sieve and Elliptic Curves

23. The Finite Fourier Transform

24. FFT and Multiplication of Numbers

25. Strassenís Fast Multiplication of Matrices Algorithm and Spreadsheet Matrix Multiplications

26 and 27 Linear Programming

28. Duality in Linear Programming

Review Topics for Second Exam

Parentheses.pdf

Term paper

Sample Topics for Term Paper