Syllabus

 

Wk Date Lec
Topic
Reading
Hws
 Collected
1
9/3
1
Introduction
Logical form and statements
1.1-1.3 and 2.1-2.2
01.pdf
02.pdf
2.1: 5, 8, 13, 17, 35, 37, 46, 52  
9/5
2
Conditional statements
Valid and invalid arguments
2.2-2.3
03.pdf
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.5
04.pdf
05.pdf
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.1-3.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.3-3.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-4.5
08.pdf
09.pdf
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-5.1
11.pdf
12.pdf
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 well-ordering principle
(covered by Prof. Tao)
5.4
14.pdf
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
15.pdf
5.5: 2, 7, 9, 12
7
-
Fall Break!
 
8
10/22
13
Recursively defined sequences
Solving recurrence relations by iteration
5.6-5.7
16.pdf
17.pdf
5.6: 8, 14, 20, 32, 40
5.7: 11, 36, 44, 52
5.4, 5.5
10/24
14
Recursion
5.8-5.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.1-6.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.3-6.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-9.4
23.pdf
24.pdf
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
r-combinations 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-10.2
29.pdf
30.pdf
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-10.7
32.pdf
33.pdf
34.pdf
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