01204211-58

Activities

• 8/20: Activity 1 - Logic 1
• 8/27: Activity 2 - Logic and Proofs
• 9/3: Activity 3 - Induction 1
• 9/10: Activity 4 - Counting 1
• 10/4: Homework 5 - Counting 2
• 10/8: Homework 6 - Number theory 1
• 10/15: Activity 7 - Number theory 2 -- Due date: 14 Dec 2015
• 11/26: Activity 8 - Polynomials and Graph theory 1 -- Due date: 14 Dec 2015
• 12/9: Homework 9 - Graph theory 2 -- Due date: 18 Dec 2015
• 12/9: Homework 10 - Graph theory 3 -- Due date: 21 Dec 2015

Topics

Week/number	Topics	Handouts	Links
1/1	Introduction, Propositions	handout1
1/2	Quantifiers	handout2	Clips: part1, part2, part3, part4
2/1	Inference rules Proof techniques 1	handout3 handout4
2/2	Proof techniques 2	handout5	Clips: part1, part2, part3
3/1	Induction 1	handout6
3/2	Induction 2	handout7	Clips: part1, part2, part3
4/1	Induction 3 Counting 1	handout8 handout9
4/2	Counting 2	handout10	Clips: part1, part2, part3, part4
5/1	Counting 3	handout11
5/2	The pigeonhole principle and the birthday problem	handout12	Clips: part1, part2, part3, part4
6/1	Binomial Coefficients 1	handout13
6/2	Binomial Coefficients 2 Fibonacci sequence	handout14 handout15	Clips (binomial coefficients 2): part1, part2
7/1	Primality testing 1	handout16
7/2	Primality testing 2	handout17
8/1	Primality testing 3	handout18
8/2	Modular arithmetic 1		External materials: Lecture notes from Berkeley CS70 Fall15 Chapter 4 sections 4.5 - 4.6 from MIT 6.042 OCW
9/1	Modular arithmetic 2 (RSA)		External materials: Lecture notes from Berkeley CS70 Fall15,
9/2	Modular arithmetic 3 (Modular multiplicative inverses)		Clips: part1, part2, part3, part4 External materials Chapter 4 sections 4.1 - 4.3 from MIT 6.042 OCW
10/1	Polynomials		External materials: Lecture notes from Berkeley CS70 Fall15
10/2	(no class - commencements)
11/1	Graphs 1 - Introduction & degrees		Materials from LPV Ch.7 sections 7.1 - 7.2. Available in this free manuscript as Ch.9, sections 9.1 - 9.2.
11/2	(cancelled)
12/1	Graphs 2 - Eulerian walks		Materials from LPV Ch.7.3.
12/2	(no class - open house)
13/1	Graphs 3 - Trees		Materials from LPV Ch.8. Available in this free manuscript as Ch.10.
13/2	Reviews with activities 8
14/1	(cancelled)
14/2	Graphs 4 - Euler's formula		Materials from LPV Ch.12.
15/1	Graphs 5 - Matching		Materials from LPV Ch.10. Available in this free manuscript as Ch.12.
15/2	(make-up) Graphs 6 - Coloring		Materials from LPV Ch.13.

Additional links

The outline of the course is inspired mainly by CS70 at Berkeley (See the recent course homepage.) More over, the course borrows a lot of exposition from other sources listed below.

• CS70: Discrete mathematics and probability theoryat Berkeley
• Mathematics for Computer Science at MIT OCW.
• Lovasz, Pelikan, Vesztergombi. Discrete Mathematics: Elementary and Beyond. Springer, 2003. See Lovasz and Vesztergombi's lecture notes (dmbook.ps)
• Matousek and Nestril. Invitation to Discrete Mathematics. 2nd Edition. Oxford Press, 2008.
• Rosen. Discrete Mathematics and Its Applications. Mcgraw-Hill.