![[Test image]](cs.gif)
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).