Syllabus
|
Wk |
Date |
Lec |
Topic |
Reading |
Hws |
Collected |
|
|
1 |
9/3 |
- |
Labor Day - No class |
|
|
|
|
|
9/5 |
1 |
Introduction Logical form and statements
|
1.1-1.3 and 2.1-2.2 |
2.1: 5, 8, 15, 17, 35, 36, 46, 54
|
|
||
|
2 |
9/10 |
2 |
Conditional statements Valid and invalid arguments |
2.2-2.3 |
2.2: 11, 15, 21, 35, 39, 41, 43, 50 2.3: 9, 13, 23, 28, 29, 32, 40 |
|
|
|
9/12 |
3 |
Digital Logic Circuits Number Systems and Circuits for Addition |
2.4-2.5
|
2.4: 2, 6, 10, 19, 31 2.5: 5, 11, 21, 24, 34, 37, 45, 47
|
2.1, 2.2, 2.3 |
||
|
3 |
9/17 |
4 |
Predicates and quantified statements |
3.1-3.2
|
3.1: 4, 5, 15, 16b, 20, 29 3.2: 2, 4b, 4d, 8, 12, 25c, 46 |
|
|
|
9/19 |
5 |
Statements containing multiple quantifiers Arguments with quantified statements |
3.3-3.4
|
3.3: 4c, 11e, 11f, 35, 40b, 43, 61 3.4: 14, 15, 19, 22, 26, 32, 34 |
|
||
|
4 |
9/24 |
6 |
Direct proof and counterexample |
4.1-4.5
|
4.1: 28, 36, 41, 56 4.2: 10, 16, 25, 32 4.3: 16, 20, 29, 39, 43, 49 4.4: 24, 51 |
2.4, 2.5, 3.1, 3.2 |
|
|
9/26 |
7 |
Indirect argument: contradiction and contraposition Two classical theorems |
4.6-4.7 |
4.6: 4, 6, 12, 22, 28, 35 4.7: 4, 10, 15, 17, 23, 24 |
|
||
|
5 |
10/1 |
8 |
Algorithms Sequences |
4.8-5.1 |
4.8: 8b, 15, 20, 24, 27 5.1: 7, 13, 17, 28, 50, 70, 79 |
4.2, 4.3, 4.4 |
|
|
10/3 |
- |
Midterm 1 (on Chapters 1-3) |
|
|
|
||
|
6 |
10/8 |
9 |
Induction |
5.2-5.3 |
5.2: 9, 11, 14, 23, 36 5.3: 15, 18, 23, 29, 35, 37 |
4.6, 4.7, 4.8. 5.1 |
|
|
|
10/10 |
10 |
Strong mathematical induction and the well-ordering principle |
5.4
|
5.4: 6, 15, 18, 19, 21, 25 |
|
|
|
7 |
10/15 |
- |
Fall break - No class |
|
|
|
|
|
10/17 |
- |
Fall break - No class |
|
|
|
||
|
|
|||||||
|
8 |
10/22 |
11 |
Correctness of Algorithms |
5.5 |
5.5: 4, 7, 9, 12 |
5.2, 5.3, 5.4 |
|
|
10/24 |
12 |
Recursively defined sequences Solving recurrence relations by iteration |
5.6-5.7 |
5.6: 6, 14, 20, 32, 40 5.7: 8, 33, 44, 52
|
|
||
|
9 |
10/29 |
13 |
Recursion |
5.8-5.9 |
5.8: 9, 15, 24 5.9: 6, 11, 14, 16, 18, 20 |
5.5, 5.6, 5.7 |
|
|
10/31 |
14 |
Basic definitions and properties of sets Set identities, proofs, Russell's paradox and the halting problem |
6.1-6.4
|
6.1: 12, 26, 30, 33c, 35c-d 6.2: 17, 22, 34, 41 6.3: 13, 20, 26, 40 6.4: 23, 25 |
|
||
|
10 |
11/5 |
15 |
Functions Defined on General Sets One-to-One and Onto, Inverse Functions Relations on Sets |
7.1, 7.2, 8.1 |
7.1: 2, 4, 16, 27, 34, 39, 44, 46 7.2: 8, 12, 13, 24, 41 8.1: 3, 8, 11, 14, 17 |
5.8, 5.9, 6.1, 6.2, 6.3, 6.4 |
|
|
11/7 |
16 |
Reflexivity, Symmetry, and Transitivity Equivalence Relations Modular Arithmetic with Applications to Cryptography |
8.2-8.4
|
8.2: 2, 14, 17, 26 8.3: 4, 16, 23, 30, 39 8.4: 5, 8, 11, 37, 40 |
|
||
|
11 |
11/12 |
17 |
Introduction to counting Possibility trees and multiplication rule |
9.1-9.3 |
9.1: 4, 13b, 19, 22, 33 9.2: 2, 14e, 15, 29, 30, 33 9.3: 2, 10, 17, 20, 21, 22, 30, 48 |
7.1, 7.2, 8.1-8.4 |
|
|
11/14 |
- |
Midterm 2 (on Chapters 4 - 6) |
|
|
|
||
|
12
|
11/19 |
18 |
Counting elements of disjoint sets: the addition rule Application: the pigeonhole principle Counting subsets of a set: combinations |
9.4-9.5
|
9.4: 8, 15, 19, 28, 32, 36 9.5: 8, 11, 16, 20, 28 |
|
|
|
11/21 |
19 |
Gambling and Probabilities |
9.8 |
9.8: 6, 15, 17, 20, 21, 23 |
|
||
|
13
|
11/26 |
20 |
r-combinations with repetition allowed The Binomial Theorem Combinatorial proofs Conditional probability, Bayes' Formula and independent events |
9.6-9.7, 9.9
|
9.6: 4, 6, 15, 17 9.7: 7, 16, 39, 42 9.9: 7, 15, 24, 28, 29, 30 |
9.4, 9.5, 9.8 |
|
|
11/28 |
21 |
Graphs Trails, Paths and Circuits |
10.1- 10.2
|
10.1: 19, 29, 30, 33, 44, 48 10.2: 2, 8, 10, 33, 48, 49 |
|
||
|
14
|
12/3 |
22 |
Matrix Representation of Graphs |
10.3- 10.4 |
10.3: 2, 5, 6, 7, 21, 23 |
9.6, 9.7, 9.9 |
|
|
|
12/5 |
|
Trees Rooted Trees |
10.5-10.6 |
10.5: 3, 6, 23, 28 10.6: 3, 17, 18, 20 |
|
|
|
15 |
12/10 |
24 |
Induction on Graphs |
|
TBA |
10.1, 10.2, 10.3, 10.5, 10.6 |
|
|
|
12/12 |
25 |
Review |
|
|
Induction on Graphs HW |
|