This schedule will be updated periodically throughout the term. Last update: Dec 6.
Readings and, in some cases, web-links are given for each of the topics listed below. Readings are from the course text unless otherwise noted.
Text: Rosen, Discrete Mathematics and Its Applications, Fourth Edition, McGraw-Hill, 1999.
| Mondays | Wednesdays | Fridays | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Date | Topics | Reading | Date | Topics | Reading | Date | Topics | Reading | ||
| Aug 30 | General Course Info; Intro to Logic | 1.1-3 | ||||||||
| Sep 2 | Logic: Propositions | 1.1-2 | Sep 4 | Logic: Quantifiers | 1.3 | Sep 6 | Logic: Proofs | 3.1 | ||
| Sep 9 | Proofs by Induction | 3.2 | Sep 11 | More Induction | 3.2 | Sep 13 | Sets & Functions | 1.4-6 | ||
| Sep 16 | Growth of Functions; Complexity of Algorithms | 1.7-8; 2.1-2; slides (see below) | Sep 18 | Number Theory (Divisibility) | 2.3 | Sep 20 | Number Theory (Euclid's Algorithm) | 2.4 | ||
| Sep 23 | Analysis of Euclid's Algorithm; Fibonacci sequence | 3.3 | Sep 25 | Applications of Number Theory | 2.5 | Sep 27 | Fermat's Little Theorem; RSA Cryptography |
2.5 | ||
| Sep 30 | RSA Cryptography; Representing Large Numbers |
2.5 | Oct 2 | Review | Oct 4 | Prelim I | ||||
| Oct 7 | Basic Counting | 4.1 | Oct 9 | Pigeonhole Principle | 4.2; Pigeonhole Problems |
Oct 11 | Permutations and Combinations | 4.3 | ||
| Oct 14 | Break | Oct 16 | Probability | 4.4 | Oct 18 | Conditional Probability | 4.5 | |||
| Oct 21 | Bayes' Formula; Independence |
4.5 | Oct 23 | Random Variables; Expected Values | 4.5 | Oct 25 | Independent Random Variables; Combinations with Repetition |
4.6 | ||
| Oct 28 | Combinations with Repetition; Inclusion / Exclusion | 4.6; 5.5 |
Oct 30 | Market Basket Data | slides (see below) | Nov 1 | Recurrence Relations | 5.1-2 | ||
| Nov 4 | Recurrence Relations | 5.1-2 | Nov 6 | Review | Nov 8 | Prelim II | ||||
| Nov 11 | Relations; Representing Relations |
6.1-3 | Nov 13 | Equivalence Relations; Closures |
6.4-5 | Nov 15 | Partial Orderings; Hasse Diagrams; Lattices |
6.6 | ||
| Nov 18 | Graphs | 7.1-2 | Nov 20 | Representing Graphs; Graph Isomorphism |
7.3 | Nov 22 | Graph Connectivity | 7.4 | ||
| Nov 25 | Graph Properties of the Web | (see below) | Nov 27 | Break | Nov 29 | Break | ||||
| Dec 1 | Planar Graphs | 7.7 | Dec 4 | Graph Coloring; Course Evaluations |
7.8 | Dec 6 | Trees; What I Do |
8.1 | ||
The Final Exam takes place at noon, Thursday, Dec 12, in Olin 155.