This page will be updated frequently with current and upcoming topics.
Any content that's colored light gray is tentative and subject to change.
Topics Day-by-Day
References to the recommended textbooks are made as follows: [LLM] is the Lehman-Leighton-Meyer book, and [Ros] is the Rosen book. The notation [LLM 4.1,4.2] means "sections 4.1 and 4.2 of the Lehman-Leighton-Meyer book", the notation [Ros Ch 6] means "chapter 6 of the Rosen book", and so on.
| # | Date | Topics | References |
|---|---|---|---|
| 1 | Th Jan 4 | Sets and relations | Slides [LLM 4.1, 4.4]; [Ros 2.1, 2.2] |
| 2 | Tu Jan 9 | Functions | Slides [LLM 4.2, 4.3, 4.5]; [Ros 2.3, 2.5] |
| 3 | Th Jan 11 | Logic and quantifiers | Slides [LLM 3.1–3.3, 3.6]; [Ros 1.1–1.5] |
| 4 | Tu Jan 16 | Styles of proof; Counting: sum principle | Slides [LLM Ch 1, 15.1, 15.2]; [Ros 1.6–1.8, 6.1] |
| 5 | Th Jan 18 | Product and division principles; Subsets | Slides [LLM 15.1–15.7] [Ros 6.1, 6.3] |
| 6 | Tu Jan 23 | Binomial coefficients; A taste of mathematical induction | Slides [LLM 15.5–15.7, 15.10, 5.1]; [Ros 6.3–6.5, 5.1] |
| X | W Jan 24 | Binomial coefficients wrap-up | |
| 7 | Th Jan 25 | Mathematical induction; Inclusion-Exclusion principle | Slides [LLM 5.2, 5.3, 15.9]; [Ros 5.2, 5.3, 8.5, 8.6] |
| 8 | Tu Jan 30 | Probability: sample spaces, events | Slides [LLM Ch 17]; [Ros 7.1, 7.2] |
| X | W Jan 31 | (Review session for Midterm 1) | |
| 9 | Th Feb 1 | Conditioning, independence | Slides [LLM Ch 18]; [Ros 7.2, 7.3] |
| 10 | Tu Feb 6 | Random variables, expectation, linearity | Slides [LLM 19.1, 19.2, 19.5]; [Ros 7.2, 7.4] |
| 11 | Th Feb 8 | Probability distributions, variance | Slides [LLM 19.3, 19.4]; [Ros 7.4] |
| 12 | Tu Feb 13 | Deviations | Notes [LLM 20.1–20.4]; [Ros 7.4] |
| 13 | Th Feb 15 | Graphs: (un)directed, degrees, walks, paths, cycles | Slides [LLM 12.1–12.4, 12.7–12.8]; [Ros 10.1–10.4] |
| 14 | Tu Feb 20 | Graph connectivity, trees, and the tree theorem | Slides, Notes [LLM 12.11]; [Ros 10.4, 11.1, 11.4] |
| X | W Feb 21 | (Review session for Midterm 2) | |
| 15 | Th Feb 22 | Digraphs, bipartite graphs, matchings, marriages | Slides [LLM 10.1–10.5, 12.5]; [Ros 10.2] |
| 16 | Tu Feb 27 | Matchings: Hall's and König's theorems | (last time's slides) [LLM 12.5]; [Ros 10.2] |
| 17 | Th Mar 1 | Planarity and coloring, Euler's theorem | Slides [LLM 12.6, 13.1–13.4]; [Ros 10.7, 10.8] |
| 18 | Tu Mar 6 | The five-color theorem; Warp up | Notes [LLM 13.4–13.6] |
The syllabus is divided into 18 units, roughly corresponding to the 18 regular classes above. Although not shown in the above plan, X-hours may be used (perhaps frequently) to catch up, as needed.
The Structure of a Class
Each class will have a three-part structure. The structure of class N is as follows:
- (about 10 minutes) recap of material from unit N-1;
- (about 40 minutes) class exercises for unit N-1;
- (about an hour) lecture on unit N.
The most novel aspect of the course will be the class exercises. These will be homework-like problems, except that you have to present your solutions in class, to your Group Ninja (our term for an in-class TA). Students will be divided into groups of about 5 students each, and each group will have a Discrete Math Ninja. Each Ninja is a past student of CS 30 who knows all of the material in the class very well. Each Ninja will work with 2 groups. The class exercises should be approached as follows.
- Each group will be seated at their own station, which will have a large table, enough chairs, a whiteboard, and a TV display that you can connect to your computer. You will present solutions either on the whiteboard or the TV display.
- There will usually be three problems assigned as class exercises. Begin by discussing solution approaches with the other students in your group. Seek help from your Ninja if you don't fully understand the exercise problems, or if you are stuck.
- About 20 minutes in, write out solution sketches and check with your Ninja that you are on the right track.
- Make corrections/changes as needed, and finalize your solutions over the next 20 minutes.
- Your Ninja will grade your work on each problem as follows. All students
in a group will get the same grade.
- (2 points) You got it right or mostly right.
- (1 point) You made a good effort but did not get it right.
- (0 points) You either didn't solve it or made a poor effort.
- If you are absent for a class, you get 0 points for all class exercise problems for that day.
Exceptions: Class 1 will not have any graded class exercises, and Unit 18 will not be represented in any class exercises.
Soon after class N, a set of practice problems for unit N will be made available on Canvas. The class exercises for unit N (to be solved during class N+1) will either be drawn from this set of practice problems or will be slight variants of problems from this set. Therefore, if you wish, you can prepare for each class by working on the practice problems in advance, either on your own, or in collaboration with your fellow students.
There is homework associated with every class. The homework for class N will consist of (1) reviewing material by reading the slides or notes posted for class N, and (2) reading related sections from one or both of the textbooks. This homework is due before class N+1. There is nothing to submit and no grade for this homework, but I assume that you will nevertheless do the homework. Accordingly, my lectures will not repeat certain definitions or basics from the textbook. Be warned that not doing the homework will make it very hard to follow along during class N+1.
There is also weekly written homework to be submitted every Wednesday night, for which each student will receive their own grades. For more on this, go to the Homework tab.