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.13.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.34.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.11.3, 2.12.3, 3.13.4, 4.14.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.17.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.18.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.15.3, 6.1, 7.17.2, 8.18.3, 8.5  
Lecture 23 7/11 
§8.4: Modular Arithmetic and the RSA Algorithm  
Lecture 24 7/12 
§9.19.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.39.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.59.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.110.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, 816, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 30 

Lecture 30 7/20 
§10.610.7 (not Dijkstra's algorithm) Graph Theory III 
§10.6: 1, 312, 15, 16, 18, 20ac §10.7: 1, 3, 58, 9, 21, 29 

Review 7/21 

Exam 3 7/24 
§9.19.6, 10.110.3, 10.510.7 (not Dijkstra's algorithm)  
Review 7/25 

Review 7/26 

Final Exam 7/27 
§1.11.3, 2.12.3, 3.13.4, 4.14.4, 4.6, 4.8, 5.15.3, 6.1, 7.17.2, 8.18.3, 8.5, 9.19.6, 10.110.3, 10.510.7 (not Dijkstra's algorithm) 