This schedule will be updated periodically throughout the term. Last update: April 30.
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, McGraw-Hill, 1999.
| Mondays | Wednesdays | Fridays | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Date | Topics | Reading | Date | Topics | Reading | Date | Topics | Reading | ||
| Jan 21 | General Course Info Intro to Induction |
3.2-3 | Jan 23 | Induction | 3.2-3 | Jan 25 | Induction | 3.2-3 | ||
| Jan 28 | Logic: propositions | 1.1-3 | Jan 30 | Logic: quantifiers | 1.1-3 | Feb 1 | Logic: proofs | 3.1 | ||
| Feb 4 | Logic: proofs | 3.1 | Feb 6 | Complexity of Algorithms | 1.8, 2.2 | Feb 8 | Number Theory, Divisibility |
2.3 | ||
| Feb 11 |
Number Theory, Euclid's Algorithm |
2.4 | Feb 13 | Multiplication, Euclid's Algorithm |
2.4 | Feb 15 | Number Theory, Chinese Remainder Theorem |
2.5 | ||
| Feb 18 | RSA Cryptography | 2.5 | Feb 20 | Review Questions | Feb 22 | Prelim I | ||||
| Feb 25 | Sets & Functions | 1.4-6 | Feb 27 | Basic Counting | 4.1 | Mar 1 | Pigeonhole Principle | 4.2 examples |
||
| Mar 4 | Permutations & Combinations | 4.3 | Mar 5 | Probability | 4.4-5 | Mar 7 | Probability | 4.4-5 | ||
| Mar 11 | Probability | 4.4-5 | Mar 12 | More Permutations & Combinations | 4.6-7 | Mar 14 | Inclusion-Exclusion | 5.5 | ||
| Mar 18 | Break | Mar 20 | Break | Mar 22 | Break | |||||
| Mar 25 | Why Probability?; Market Basket Data |
see below | Mar 27 | Market Basket Data | see below | Mar 29 | Market Basket Data | see below | ||
| Apr 1 | Relations | 6.1-6 | Apr 3 | Review | Apr 5 | Prelim II | ||||
| Apr 8 | Relations | 6.1-6 | Apr 10 | Relations | 6.1-6 | Apr 12 | Graphs | 7.1-4 | ||
| Apr 15 | Graphs | 7.1-4 | Apr 17 | Graphs | 7.1-4 | Apr 19 | Planar Graphs | 7.7 | ||
| Apr 22 | Graph Properties of the Web | see below | Apr 24 | Graph Coloring | 7.8 | Apr 26 | Trees | 8.1,3,5 | ||
| Apr 29 | Trees | 8.1,3,5 | May 1 | What I Do Course Evaluation |
May 3 | Course Review | ||||
The Final Exam takes place on Tuesday, May 14 at noon.
Market Basket Data is a pdf file that contains the slides used in the lecture on Friday, Mar 29. The following two papers are the source for the lecture material on Market Basket Data:
The following paper is the source for the lecture material on the Graph Properties of the Web