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 |