**Announcements:**

- 12/06/07: Review for final exam in recitation 12/7/07.
- 11/30/07:
**Final exam in on Tuesday, 12/11/07, 9 am to noon** - 11/30/07: The recitation on 12/7/07 will be a review class.
- 11/26/07: Homework 6 has been posted. It's due on 12/5/07/.
- 11/8/07: Homework 5 has been posted. Its due on 11/19/07.
- 10/31/07: Quiz 2 is on Friday 11/02/07.
- 10/17/07: Homework 4 has been posted and it is due on 10/30/07.
- 10/03/07: Homework 3 has been posted and it is due on 10/15/07.
- 09/27/07: Quiz 1 is on Friday 08/28/07.
- 09/27/07: Homework 2 is due on Friday 09/28/07.
- 09/08/07: Homework 1 is due on Monday 09/17/07.
- 09/10/07: Bruce's office hours this week are after class until 5 pm.

**Administration:**

*Instructor*: Bruce Maggs

*Teaching Assistant*: Urmi Majumder

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

*Lectures Location*: LSRC D 243

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

*Recitation Location*: LSRC D 243

*Office Hours*:

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

Urmi Majumder: *Tuesday, 11:00-12:00 noon in LSRC D 104*

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

Aug 29 | Deterministic Finite Automata | Lecture 2 | 10.2-10.4 | |

Sept 5 | Solving problems and writing proofs | Lecture 3 | Homework 1 | |

Sept 7 | Recitation | |||

Sept 10 | Inductive Reasoning | Lecture 4 | 3.1-3.2 | |

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

Sept 14 | Recitation | |||

Sept 17 | Counting I: Correspondences and Choice Trees | Lecture 6 | 4.1-4.3 | |

Sept 19 | Counting II: Recurring Problems and Correspondences | Lecture 7 | 4.1-4.3 | Homework 2 |

Sept 21 | Counting III | Lecture 8 | 4.6 | |

Sept 24 | Recitation | |||

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

Sept 28 | QUIZ 1 |
|||

Oct 1 | Probability Theory: Counting in Terms of Proportions | Lecture 10 | 4.4-4.5 | |

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

Oct 5 | Recitation | |||

Oct 8 | NO CLASSES, Fall break |
|||

Oct 10 | Random Walks | Lecture 12 | ||

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

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

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

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

Oct 24 | Randomness and Computation | Lecture 16 | ||

Oct 26 | Recitation | |||

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

Oct 31 | Group Theory | Lecture 18 | ||

Nov 2 | QUIZ 2 |
|||

Nov 5 | Graphs | Lecture 19 | ||

Nov 7 | Graphs II | Lecture20 | Homework 5 | |

Nov 9 | Recitation | |||

Nov 12 | The Big Oh | Lecture21 | ||

Nov 14 | Grade School Revisited: How to Multiply Two Numbers | Lecture22, Lecture22b | ||

Nov 16 | Recitation | |||

Nov 19 | Cantor's Legacy: Infinity and Diagonalization | Lecture23 | ||

Nov 21 | NO CLASSES, Thanksgiving recess |
|||

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

Nov 26 | Turing's Legacy: The Limits of Computation | Lecture24 | Homework 6 | |

Nov 28 | Godel's Legacy: What is a Proof? | Lecture25 | ||

Nov 30 | Recitation | |||

Dec 3 | Complexity Theory: Reductions Between Computational Problems | Lecture26 | ||

Dec 5 | Complexity Theory: The P vs. NP Question | Lecture27 | ||

Dec 7 | Recitation | |||

Dec 11 | FINAL EXAM 9:00am-noon |

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