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

Bruce Maggs:

Mahanth Gowda:

Nicholas Gordon:

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.

Sep 27: Sample Quizzes to help prepare for Quiz-1, from 2010 and 2011. Solutions are here - 2010 and 2011.

Oct 23: Sample Quizzes to help prepare for Quiz-2, from 2010 and 2011. Solutions are here - 2010 and 2011

Nov 20: Sample Quiz to help you prepare for Quiz-3, from 2011. Solutions are here - 2011

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

Date | Lecture Topic | Slides | Reading | Assignment | |

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

Aug 30 | Deterministic Finite Automata | Lecture 2 | 13.2-13.4 | ||

Aug 31 | NO CLASSES | ||||

Sept 4 | Solving problems and writing proofs | Lecture 3 | 1.7-1.8 | Homework 1 | |

Sept 6 | Inductive Reasoning | Lecture 4 | 5.1-5.3 | ||

Sept 7 | Recitation: DFA | ||||

Sept 11 | Ancient Wisdom: Unary and Binary | Lecture 5 | 4.1-4.2 | ||

Sept 13 | Counting I: Correspondences and Choice Trees | Lecture 6 | 6.1-6.3 | ||

Sept 14 | Recitation: Proofs | ||||

Sept 18 | Counting II: Recurring Problems and Correspondences | Lecture 7 | 6.1-6.3, 2.3 | ||

Sept 20 | Counting III | Lecture 8 | 6.4 | Homework 2 | |

Sept 21 | Recitation : Counting | ||||

Sept 25 | Probability I: Counting in Terms of Proportions | Lecture 9 | 7.1-7.2 | ||

Sept 27 | Probability II: Great Expectations | Lecture 10 | 7.4 | ||

Sept 28 | Recitation: Quiz Preperation | ||||

Oct 2 | QUIZ 1 | ||||

Oct 4 | Random Walks | Lecture 11 | |||

Oct 5 | Recitation | ||||

Oct 9 | Ancient Wisdom: On Raising A Number to a Power | Lecture 12 | Homework 3 | ||

Oct 11 | Euclid's Algorithm and Continued Fractions | Lecture 13 | 4.3 | ||

Oct 12 | Recitation | ||||

Oct 16 | NO CLASSES | ||||

Oct 18 | Randomness and Computation | Lecture 14 | 4.4 (Fermat's Little Theorem) | ||

Oct 19 | Recitation | ||||

Oct 23 | Fibonacci Numbers, Polynomial Coefficients, Vector Programs | Lecture 15 | |||

Oct 25 | Modular Arithmetic and the RSA Cryptosystem | Lecture 16 | 4.1-4.6 | Homework 4 | |

Oct 26 | Recitation | ||||

Oct 30 | Group Theory | Lecture 17 | |||

Nov 1 | Graphs | Lecture 18 | 10.1-10.3 (Graph Representation only), 10.7-10.8, 11.1, 11.4 | ||

Nov 2 | Recitation | ||||

Nov 6 | Graphs II | Lecture 19 | 11.5, 10.2 | ||

Nov 8 | QUIZ 2 | ||||

Nov 9 | Recitation | ||||

Nov 13 | How Computers Really Do Arithmetic | Lecture 20 | |||

Nov 15 | The Big Oh | Lecture 21 | 3.2 | ||

Nov 16 | NO Classes | ||||

Nov 20 | Cantor's Legacy: Infinity and Diagonalization | Lecture 22 | 2.5 | Homework 5 | |

Nov 22 | NO CLASSES, Thanksgiving recess | ||||

Nov 23 | NO CLASSES, Thanksgiving recess | ||||

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

Nov 29 | Godel's Legacy: What is a Proof? | Lecture 24 | |||

Nov 30 | Recitation | ||||

Dec 4 | QUIZ 3 | ||||

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

Dec 7 | Recitation | ||||

Dec 11 | FINAL EXAM 2:00pm-5:00pm | Loc: LSRC D106 |