This course is meant as a first introduction to discrete mathematics with emphasis on its use in computer science. Topics include: Propositional and Predicate Logic, Proof Techniques, Sequences, Mathematical Induction, Set Theory, Functions and Relations, Counting and Probability, and Graph Theory.
| Subject | Recommended Exercises | |||
|---|---|---|---|---|
| Week 1 | Lecture 1 6/5 |
Syllabus §1.1: Variables and Statements |
§1.1: 5, 10, 12, 13 | |
| Lecture 2 6/6 |
§1.2, 1.3: The Language of Sets, Relations, and Functions |
§1.2: 1, 2b, 3, 4e, 6, 7ae, 8ad, 9b, 11 §1.3: 2, 3, 7, 8, 9, 11, 13, 19 |
||
| Lecture 3 6/7 |
§2.1: Propositional Logic I | §2.1: 1, 5a, 6, 11, 14, 15, 16, 17, 21, 25, 27, 29, 36, 37, 40, 43, 52 | ||
| Lecture 4 6/8 |
§2.2: Propositional Logic II | §2.2: 1, 5, 9, 12, 13b, 16, 20ab, 21, 22a, 23a, 24, 29, 32, 33, 34, 37, 38, 39, 40, 42, 44, 46d, 47, 49, 50a | ||
| Lecture 5 6/9 |
§2.3: Propositional Logic III | §2.3: 3, 6, 8, 11, 12a, 14, 22, 23, 26, 28, 36, 37, 38ad, 39, 40, 41, 44 | ||
| Week 2 | Lecture 6 6/12 |
§3.1-3.2: Predicate Logic I |
§3.1: 1abd, 3, 4ac, 8ac, 10, 11, 18abe, 23ab, 24a, 27ab §3.2: 1, 3c, 7, 8, 18, 19, 28, 29, 37, 38, 43, 45, 47, 48 |
|
| Lecture 7 6/13 |
§3.3: Predicate Logic II | §3.3: 3ab, 7, 10acf, 13, 16, 20ab, 24a, 27, 28, 38, 39, 40ab, 44ac, 50, 51, 55, 56, 59, 61 | ||
| Lecture 8 6/14 |
§3.4: Predicate Logic III | §3.4: 2, 6, 8, 9, 13, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 33, 34 | ||
| Lecture 9 6/15 |
§4.1: Proof Methods I |
§4.1: 2, 11, 13, 14, 16, 17, 22, 23, 31, 33, 34, 35, 41, 44, 47, 50, 55 §4.2: 4, 7, 10, 11, 18, 19, 21, 23, 24, 28, 31, 35, 38 |
||
| Lecture 10 6/16 |
§4.2: Proof Methods I | §4.2: 4, 7, 10, 11, 18, 19, 21, 23, 24, 28, 31, 35, 38 | ||
| Week 3 | Lecture 11 6/19 |
§4.3-4.4: Proof Methods II |
§4.3: 12, 13, 14, 15, 18, 24, 28, 34, 38, 43, 44 §4.4: 3, 7, 18, 19, 20, 22, 23, 25, 28, 32, 35, 47 |
|
| Lecture 12 6/20 |
§4.6,4.8: Proof Methods III |
§4.6: 5, 7, 10, 11, 15, 17, 21, 22, 23, 34 §4.8: 4, 5, 6, 7, 9, 13, 16, 23ab, 24b, 25ac, 26 |
||
| Exam 1 6/21 |
§1.1-1.3, 2.1-2.3, 3.1-3.4, 4.1-4.4, 4.6, 4.8 | |||
| Lecture 13 6/22 |
§5.1: Sequences | §5.1: 14, 16, 27, 28, 37, 38, 40, 41, 51, 52, 55, 58, 59, 61, 69, 70, 80ab, 81, 83, 84, 86, 88, 89 | ||
| Lecture 14 6/23 |
§5.2: Mathematical Induction I | §5.2: 1, 2, 3, 4, 5, 26 | ||
| Week 4 | Lecture 15 6/26 |
§5.2: Mathematical Induction II | §5.2: 6, 7, 8, 10, 13, 14, 20, 23, 28, 29, 32 | |
| Lecture 16 6/27 |
§5.3: Mathematical Induction III | §5.3: 1, 3, 6, 8, 10, 13, 16, 17, 24, 25, 29, 30 | ||
| Lecture 17 6/28 |
§6.1: Set Theory | §6.1: 1af, 2, 3, 6, 7c, 10, 11, 13dfi, 14b, 15, 17ad, 18, 21, 23, 27bd, 29, 31, 32ab, 35bd, 36, 37 | ||
| Lecture 18 6/29 |
§6.2: Set Properties | §6.2: 1, 3, 4, 6, 7, 8, 11, 15, 18, 19, 20, 21, 22, 26, 34, 36 | ||
| Lecture 19 6/30 |
§7.1-7.2: Functions |
§7.1: 1, 3, 4a, 5abd, 6, 7, 9, 11ab, 12, 14, 15, 18, 21, 25a, 26a, 28ab, 29a, 30, 33, 35, 37, 38, 43, 44, 51abc §7.2: 1, 6, 7a, 8, 9, 10, 12, 13ab, 15, 21, 22, 28, 29, 36, 37, 38, 42, 43, 44, 45, 49 |
||
| Week 5 | Lecture 20 7/3 |
§8.1-8.2: Relations |
§8.1: 1a, 3, 4ab, 5ab, 8c, 9, 10, 12, 14, 15, 19, 20, 21, 23 §8.2: 1, 3, 5, 6, 9, 10, 11, 12, 14, 23, 25, 26, 28, 34, 35, 37, 43, 44, 51, 53 |
|
| Holiday 7/4 |
||||
| Lecture 21 7/5 |
§8.3: Equivalence Relations | §8.3: 1, 3, 5, 6, 7, 8, 9, 10, 15, 18, 19a, 21, 22, 23, 24, 25, 28, 29, 30, 34, 36, 37, 39, 44abd | ||
| Lecture 22 7/6 |
§8.5: Partial Order Relations | §8.5: 1ab, 2, 3, 4, 5, 6, 8, 9, 10, 11abd, 13, 14a, 16a, 17ab, 18, 19, 21, 22, 24, 25, 26, 27, 30, 31, 32, 35, 37, 38, 39, 42, 44, 46, 47, 49, 50a | ||
| Review 7/7 |
||||
| Week 6 | Exam 2 7/10 |
§5.1-5.3, 6.1, 7.1-7.2, 8.1-8.3, 8.5 | ||
| Lecture 23 7/11 |
§8.4: Modular Arithmetic and the RSA Algorithm | |||
| Lecture 24 7/12 |
§9.1-9.2 Counting & Probability I |
§9.1: 2, 3, 5, 7, 12, 13ab, 14, 16, 18, 19, 20, 21, 24, 25, 26, 28, 29, 31, 32 §9.2: 1, 4, 6, 7, 8, 9, 10, 11ab, 12, 13ab, 14, 15, 16, 18, 19, 22, 24, 27, 28, 32, 34, 37a, 38, 39, 47 |
||
| Lecture 25 7/13 |
§9.3-9.4 Counting & Probability II | §9.3: 1, 3, 4, 6, 8, 9, 11, 13, 14, 15, 16, 25, 29, 31, 32, 33, 34, 35, 37 | ||
| Lecture 26 7/14 |
§9.4 Counting & Probability III | §9.4: 1, 3, 5, 9, 12, 13, 14, 17, 19, 22, 23, 26, 28, 29, 31 | ||
| Lecture 27 7/17 |
§9.5-9.6 Counting & Probability IV |
§9.5: 1, 3, 5ab, 6, 7, 9, 12, 13ad, 15, 16, 19, 21, 22, 23, 24, 25, 27 §9.6: 1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 16, 18, 20 |
||
| Lecture 28 7/18 |
§10.1-10.2 Graph Theory I |
§10.1: 1, 3, 6, 8, 9, 12, 13, 15, 17, 18, 22, 23, 27, 28, 29, 36, 37abef, 39, 40b, 42 §10.2: 1, 3, 4, 6, 8ac, 9, 12, 17, 18, 19, 22, 23, 24, 26, 30, 31, 33, 36 |
||
| Lecture 29 7/19 |
§10.3, 10.5 Graph Theory II |
§10.3: 1a, 2a, 3, 4acd, 6, 7, 8a, 9, 10abfi, 12, 19, 20 §10.5: 1a, 2a, 3, 4, 7a, 8-16, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 30 |
||
| Lecture 30 7/20 |
§10.6-10.7 (not Dijkstra's algorithm) Graph Theory III |
§10.6: 1, 3-12, 15, 16, 18, 20ac §10.7: 1, 3, 5-8, 9, 21, 29 |
||
| Review 7/21 |
||||
| Exam 3 7/24 |
§9.1-9.6, 10.1-10.3, 10.5-10.7 (not Dijkstra's algorithm) | |||
| Review 7/25 |
||||
| Review 7/26 |
||||
| Final Exam 7/27 |
§1.1-1.3, 2.1-2.3, 3.1-3.4, 4.1-4.4, 4.6, 4.8, 5.1-5.3, 6.1, 7.1-7.2, 8.1-8.3, 8.5, 9.1-9.6, 10.1-10.3, 10.5-10.7 (not Dijkstra's algorithm) |