This page will be updated frequently with current and upcoming topics.
Topics Day-by-Day
| # | Date | Topics | References |
|---|---|---|---|
| 1 | Th Jan 5 | Sets and relations | Slides |
| 2 | Tu Jan 10 | Functions | Slides |
| 3 | Th Jan 12 | Logic and quantifiers | Slides |
| 4 | Tu Jan 17 | Styles of proof; Counting: sum principle | Slides |
| 5 | Th Jan 19 | Product and division principles; Subsets | Slides |
| 6 | Tu Jan 24 | Binomial coefficients; A taste of mathematical induction | Slides |
| 7 | Th Jan 26 | Mathematical induction; Inclusion-Exclusion principle | Slides |
| 8 | Tu Jan 31 | Probability: sample spaces, events | Slides |
| X | W Feb 1 | (Review session for Midterm 1) | |
| 9 | Th Feb 2 | Conditioning, independence | Slides |
| 10 | Tu Feb 7 | Random variables, expectation, linearity | Slides |
| 11 | Th Feb 9 | Probability distributions, variance | Slides |
| 12 | Tu Feb 14 | Deviations | Notes |
| 13 | Th Feb 16 | Graphs: (un)directed, degrees, walks, paths, cycles | Slides |
| 14 | Tu Feb 21 | Graph connectivity, trees, and the tree theorem | Slides, Notes |
| X | W Feb 22 | (Review session for Midterm 2) | |
| 15 | Th Feb 23 | Bipartite graphs, matchings, marriages | Slides |
| 16 | Tu Feb 28 | Matchings: Hall's and König's theorems | (last time's slides) |
| 17 | Th Mar 2 | Planarity and coloring, Euler's theorem | Slides |
| 18 | Tu Mar 7 | The five-color theorem | Notes |
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, except for the 1st and the 18th, 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 TA. Students will be divided into groups of about 5 students each, and each group will have a TA. Each TA 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 TA 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 TA that you are on the right track.
- Make corrections/changes as needed, and finalize your solutions over the next 20 minutes.
- Your TA 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 (indicated in the slides/notes) 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 Monday night. This will consist of about three problems either drawn from or variants/extensions of the previous week's set of practice problems. Each individual student will receive their own grades for the weekly homework.