Wk  Date  Lec  Topic 
Reading 
Hws 
Collected 

1  9/3 
1 
Introduction Logical form and statements 
2.1: 5, 8, 13, 17, 35, 37, 46, 52  
9/5 
2 
Conditional statements Valid and invalid arguments 
2.2: 10, 15, 21, 35, 43, 50 2.3: 10, 13, 23, 28, 29, 32, 40 

2  9/10 
3 
Digital Logic Circuits Number Systems and Circuits for Addition 
2.4: 2, 6, 10, 21, 31
2.5: 5, 11, 21, 26, 34, 37, 45, 47 
2.1, 2.2, 2.3 

9/12 
4 
Predicates and quantified statements 
3.13.2 06.pdf 
3.1: 4c, 5b, 15, 16b, 20, 29 3.2: 2, 4b, 4d, 8, 14, 25c, 44 

3  9/17 
6 
Statements containing multiple quantifiers Arguments with quantified statements 
3.33.4
07.pdf 
3.3: 4c, 11e, 38, 40b, 43, 61 3.4: 14, 15, 19, 22, 27, 32 
2.4, 2.5, 3.1, 3.2 
9/19 
7 
Direct proof and counterexample 
4.1: 28, 37, 41, 56 4.2: 10, 17, 25, 32 4.3: 16, 20, 39, 43, 49 4.4: 25, 52 

4  9/24 
8 
Indirect argument: contradiction and contraposition Two classical theorems 
4.6: 4, 7, 12, 22, 28, 35 4.7: 4, 8, 15, 17, 24 
3.3, 3.4, 4.1, 4.2, 4.3, 4.4


9/26 
9 
Algorithms Sequences 
4.8: 8b, 16, 20, 24, 28 5.1: 7, 15, 17, 28, 50, 79 

5  10/1 
10 
Induction 
5.2: 7, 11, 14, 23, 36 5.3: 10, 17, 23, 29, 35, 37 
4.6, 4.7, 4.8, 5.1 

10/3 
11 
Strong mathematical induction and the wellordering principle (covered by Prof. Tao) 
5.4: 2, 15, 18, 19, 21, 25 

6 
10/8 
 
Midterm 1 
5.2, 5.3


10/10 
12 
Correctness of Algorithm 
5.5: 2, 7, 9, 12 

7 
 
Fall Break! 

8  10/22 
13 
Recursively defined sequences Solving recurrence relations by iteration 
5.6: 8, 14, 20, 32, 40 5.7: 11, 36, 44, 52 
5.4, 5.5


10/24 
14 
Recursion 
5.85.9 18.pdf 
5.8: 10, 14, 24 5.9: 8, 11, 14, 16, 18, 20 

9  10/29 
15 
Basic definitions of set theory Properties of sets 
6.16.2 19.pdf 
6.1: 12, 25, 30, 33, 35 6.2: 14, 22, 31, 41 
5.6, 5.7, 5.8, 5.9 
10/31 
16 
Set identities, proofs, Russell's paradox and the halting problem 
6.36.4 20.pdf 
6.3: 7, 20, 26, 37 6.4: 23, 25 

10  11/5 
17 
Introduction to counting Possibility trees and multiplication rule 
9.1: 6, 13b, 19, 22, 33 9.2: 2, 14c, 15, 29, 30, 33 
6.1, 6.2, 6.3, 6.4


11/7 
18 
Counting elements of disjoint sets: the addition rule Application: the pigeonhole principle 
9.3: 2, 10, 17, 20, 21, 22, 30, 49 9.4: 11, 16, 19, 30, 32, 36 

11 
11/12 
19 
Counting subsets of a set: combinations rcombinations with repetition allowed 
9.5: 7, 11, 16, 20, 28 9.6: 4, 6, 15, 18 
9.1, 9.2, 9.3, 9.4


11/14 
20 
The Binomial Theorem Combinatorial proofs 
9.7 26.pdf 
9.7: 7, 16, 39, 42 

12  11/19 
 
Midterm 2 

11/23 
21 
Gambling and Probabilities 
9.8 27.pdf 
9.8: 5, 15, 18, 20, 21, 23 

13 
11/26 
22 
Conditional probability, Bayes' Formula and independent events 
9.9 28.pdf 
9.9: 15, 24, 28, 29, 30, 33 
9.5, 9.6

11/28 
 
Happy Thanksgiving! 

14 
12/3 
23 
Graphs Trails, Paths and Circuits (covered by Prof. Tao) 
10.1: 20, 28, 30, 33, 44, 48 10.2: 2, 8, 11, 35, 48, 49 
9.7, 9.8, 9.9


12/5 
24 
Matrix Representation of Graphs 
10.3: 4, 5, 6, 7, 21, 23 

15 
12/10 
25 
Class cancelled due to snow 

12/12 
26 
Trees Rooted Trees Spanning Trees and Shortest Paths 
10.5: 3, 6, 23, 26 10.6: 3, 14, 17, 20 10.7: 10, 14, 19, 21, 27 
10.1, 10.2, 10.3 