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

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
9/1	Modular arithmetic 2 (RSA)
9/2	Modular arithmetic 3 (Modular multiplicative inverses)		Clips: part1, part2, part3, part4
10/1
10/2
11/1	Graphs 1 - Introduction & degrees
11/2	(cancelled)
12/1	Graphs 2 - Eulerian walks
12/2	(no class - open house)
13/1	Graphs 3 - Trees

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.