This is a self-contained course. The lectures for this course are primarily developed by Professor Steven Rudich.

**Announcements:**

- 11/22/10: Homework 6 has been posted. It's due on Dec. 8th.
- 10/25/10: Homework 4 has been posted to the blackboard. It's due on Nov. 3rd. Please submit it to the BLACKBOARD.
- 10/04/10: Homework 3 has been posted. It's due on Oct. 18th. Please submit it to the BLACKBOARD.
- 10/04/10: Quiz 1 grades have been posted on blackboard.
- 09/20/10: Homework 2 has been posted. It's due on Sept. 29th.
- 09/19/10: Please bring your homework 1 to tomorrow's class.
- 09/09/10: Homework 1 has been posted. It's due on Sept. 20th.

Bruce Maggs:

Yin Lin:

Please turn in your homeworks at the beginning of the class on the day it is due. There is a penalty of seven points a day late on the homework. Regarding collaboration/cheating policy, you may NOT share written work.

We reuse homework problems.

Date | Lecture Topic | Slides | Reading | Assignment |

Aug 30 | Pancakes with a problem | Lecture 1 | ||

Sept 1 | Deterministic Finite Automata | Lecture 2 | 12.2-12.4 | |

Sept 3 | NO CLASSES | |||

Sept 6 | Solving problems and writing proofs | Lecture 3 | ||

Sept 8 | Inductive Reasoning | Lecture 4 | 4.1-4.2 | |

Sept 10 | Recitation: DFA | Homework 1 | ||

Sept 13 | Ancient Wisdom: Unary and Binary | Lecture 5 | 3.6 starting with "Representations of Integers" | |

Sept 15 | Counting I: Correspondences and Choice Trees | Lecture 6 | 5.1-5.3 | |

Sept 17 | Recitation: Proofs | |||

Sept 20 | Counting II: Recurring Problems and Correspondences | Lecture 7 | 5.1-5.3 | Homework 2 |

Sept 22 | Counting III | Lecture 8 | 5.4 | |

Sept 24 | Recitation : Counting | |||

Sept 27 | Probability I: Counting in Terms of Proportions | Lecture 9 | 4.4-4.5 | |

Sept 29 | Probability II: Great Expectations | Lecture 10 | 4.4-4.5 | |

Oct 1 | Recitation: Quiz Preperation | |||

Oct 4 | QUIZ 1 | |||

Oct 6 | Random Walks | Lecture 11 | Homework 3 | |

Oct 8 | Recitation | |||

Oct 11 | NO CLASSES, Fall break | |||

Oct 13 | Ancient Wisdom: On Raising A Number to a Power | Lecture 12 | ||

Oct 15 | NO CLASSES | |||

Oct 18 | Euclid's Algorithm and Continued Fractions | Lecture 13 | 2.3-2.4 | |

Oct 20 | Fibonacci Numbers, Polynomial Coefficients, Vector Programs | Lecture 14 | ||

Oct 22 | Recitation | |||

Oct 25 | Randomness and Computation | Lecture 15 | Homework 4 | |

Oct 27 | Modular Arithmetic and the RSA Cryptosystem | Lecture 16 | ||

Oct 29 | Recitation | |||

Nov 1 | Group Theory | Lecture 17 | ||

Nov 3 | Graphs | Lecture 18 | ||

Nov 5 | Recitation | |||

Nov 8 | Graphs II | Lecture 19 | ||

Nov 10 | QUIZ 2 | |||

Nov 12 | No Classes | |||

Nov 15 | The Big Oh | Lecture 20 | Homework 5 | |

Nov 17 | How Computers Really Do Arithmetic | Lecture 21 | ||

Nov 19 | No Classes | |||

Nov 22 | Cantor's Legacy: Infinity and Diagonalization | Lecture 22 | Homework 6 | |

Nov 24 | NO CLASSES, Thanksgiving recess | |||

Nov 26 | NO CLASSES, Thanksgiving recess | |||

Nov 29 | Turing's Legacy: The Limits of Computation | Lecture 23 | ||

Dec 1 | Godel's Legacy: What is a Proof? | Lecture 24 | ||

Dec 3 | NO Classes | |||

Dec 6 | Complexity Theory: Reductions Between Computational Problems, The P vs. NP Question | Lecture 25 | ||

Dec 8 | Recitation | |||

Dec 14 | FINAL EXAM 9:00am-NOON | Loc: LSRC D106 |

Note: All readings are from *Discrete Mathematics and its Applications* by Kenneth H. Rosen, published by McGraw-Hill (6th edition).