**Administration:**

*Instructor*: Bruce Maggs

*Teaching Assistant*: Souvik Sen

*Lectures Time*: Monday and Wednesday, 2:50 pm -4:05 pm

*Lectures Location*: Languages 211

*Recitation Time*: Friday, 2:50 pm -4:05 pm

*Recitation Location*: Sociology-Psycology 127

*Office Hours*:

Bruce Maggs: *Monday and Wednesday after class in LSRC D324*

Souvik Sen: *Friday 11:30-12:30 noon in Hudson 214*

**Grading:**

*Homeworks (40%), Quizzes (30%) and Final (30%)*

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 24 | Pancakes with a problem | Lecture 1 | ||

Aug 26 | Deterministic Finite Automata | Lecture 2 | 12.2-12.4 | Homework 1 |

Aug 28 | Recitation | |||

Aug 31 | Solving problems and writing proofs | Lecture 3 | ||

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

Sept 4 | Recitation | |||

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

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

Sept 11 | Recitation | |||

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

Sept 16 | Counting III | Lecture 8 | 5.4 | |

Sept 18 | Recitation | |||

Sept 23 | The Mathematics of 1950's Dating | Lecture 9 | ||

Sept 25 | Probability Theory: Counting in Terms of Proportions | Lecture 10 | 4.4-4.5 | |

Sept 28 | QUIZ 1 |
|||

Sept 30 | Probability Theory: Great Expectations | Lecture 11 | 4.4-4.5 | Homework 3 |

Oct 2 | Recitation | |||

Oct 5 | NO CLASSES, Fall break |
|||

Oct 7 | Random Walks | Lecture 12 | ||

Oct 9 | Recitation ; Mid-semester grades due | |||

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

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

Oct 16 | Recitation | |||

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

Oct 21 | Randomness and Computation | Lecture 16 | Homework 4 | |

Oct 26 | Modular Arithmetic and the RSA Cryptosystem | Lecture 17 | ||

Oct 28 | Group Theory | Lecture 18 | ||

Oct 30 | QUIZ 2 |
|||

Nov 2 | Graphs | Lecture 19 | ||

Nov 4 | Graphs II | Lecture 20 | Homework 5 | |

Nov 6 | Recitation | |||

Nov 9 | The Big Oh | Lecture 21 | ||

Nov 11 | How Computers Really Do Arithmetic | Lecture 22 | ||

Nov 16 | Grade School Revisited: How to Multiply Two Numbers | Lecture 22 | ||

Nov 18 | Cantor's Legacy: Infinity and Diagonalization | Lecture 23 | ||

Nov 20 | Recitation | |||

Nov 23 | Turing's Legacy: The Limits of Computation | Lecture 24 | Homework 6 | |

Nov 25 | NO CLASSES, Thanksgiving recess |
|||

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

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

Nov 20 | Recitation | |||

Dec 10 | FINAL EXAM 2:00pm-5:00pm |
Languages 211 |

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