This page will be updated frequently with current and upcoming topics.
Topics Day-by-Day
| # | Date | Topics | References |
|---|---|---|---|
| 1 | Th Sep 17 | Sets and relations | Slides |
| 2 | Tu Sep 22 | Functions | Slides |
| 3 | Th Sep 24 | Logic and quantifiers | Slides |
| 4 | Sa Sep 26 | Styles of proof; Counting: sum principle | Slides |
| 5 | Tu Sep 29 | Product and division principles; Subsets | Slides |
| 6 | Th Oct 1 | Mathematical induction | Summary |
| 7 | Tu Oct 6 | More induction; Binomial coefficients | Induction slides, Binom coeff slides |
| X | We Oct 7 | (Review session for Midterm 1) | |
| 8 | Th Oct 8 | Inclusion-exclusion principle | Slides |
| 9 | Tu Oct 13 | Probability: sample spaces, events | Slides |
| 10 | Th Oct 15 | Conditioning, independence | Slides |
| 11 | Tu Oct 20 | Random variables, expectation, linearity | Slides |
| 12 | Th Oct 22 | Probability distributions, variance | Slides |
| 13 | Tu Oct 27 | Deviations | Notes |
| X | We Oct 28 | (Review session for Midterm 2) | |
| 14 | Th Oct 29 | Graphs: (un)directed, degrees, walks, paths, cycles | Slides |
| 15 | Tu Nov 3 | Graph connectivity, equivalence relations, trees | Slides, Supplementary notes |
| 16 | Th Nov 5 | Tree theorem | Slides |
| 17 | Tu Nov 10 | Bipartite graphs, matchings, marriages | Slides |
| X | We Nov 11 | Matchings: Hall's and König's theorems | |
| 18 | Th Nov 12 | Planarity and coloring, Euler's theorem | Slides |
| 19 | Tu Nov 17 | The five-color theorem | Notes |
The syllabus is divided into 19 units, roughly corresponding to the 19 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 19th, 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 19 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.