## CS173: Discrete Structures

The optional textbook for this course is Discrete Mathematics and its Applications by Kenneth Rosen. You may find it helpful if you'd like more detail about a topic, or a presentation of the same ideas from a different viewpoint. Here are the sections of Rosen approximately corresponding to the topics in the CS 173 textbook.

Text chapter Rosen 6th Rosen 7th
1: Math review Appendix 2 Appendix 2
2: Logic 2.4, end of 2.3
1.1
2.4, end of 2.3
1.1
3: Proofs 1.6 1.7
4: Number Theory 3.4, 3.5, 3.6, appendix 3 4.1, 4.2, 4.3, appendix 3
5: Sets 2.1,2.2,5.1 2.1,2.2,6.1
6: Relations 8.1,8.3,8.5 9.1,9.3,9.5
7: Functions/onto 1.4,2.3 1.5,2.3
8: Functions/one-to-one 2.3,5.2,some of 5.3 2.3,6.2,some of 6.3
9: Graphs dispersed in chapter 9, terminology differs from lecture notes dispersed in chapter 10, terminology differs from lecture notes
10: 2-way Bounding not in Rosen not in Rosen
11: Induction 4.1,4.2 5.1,5.2
12: Recursive definition 4.3 5.3
13: Trees 10.1,12.1 11.1,13.1
14: Big-O 3.2,7.1,7.2 3.2,8.1,8.2
15: Algorithms and 16: NP 3.1, 3.3, 4.4, and 7.1 3.1, 3.3, 5.4, part of 2.4 on Recurrence Relations, and 8.1
17: Proof by Contradiction 1.6 1.7
18: Sets of Sets 2.1,5.3,5.4,5.5,8.5 2.1,6.3,6.4,6.5,9.5
19: State Diagrams 12.3 13.3
20: Countability 2.4 2.4
21: Planar Graphs 9.7,9.8 10.7,10.8