### CS 173 [B], Fall 2012

# Lectures

### Lectures so far

- 00: Aug 28. Introduction.

[no pre-lecture preparation] slides [slideshow|print] - 01: Aug 30. Logic.

[watch video 1 & video 2, read 2.1-2.10, take quiz on Moodle] slides [slideshow|print] - 02: Sep 4. Logic (ctd).

[watch video 3, read 2.11 - 2.17, take quiz on Moodle] slides [slideshow|print] - 03: Sep 6. Logic & Proofs.

[read chapter 3, take quiz on Moodle] slides [slideshow|print] - 04: Sep 11. Proofs & Numbers.

[read chapter 3, and 4.1 - 4.9, take quiz on Moodle] slides [slideshow|print] - 05: Sep 13. Numbers.

[read chapter 4, watch video clip, take quiz on Moodle] slides [slideshow|print] - 06: Sep 18. Sets.

[read chapter 5, take quiz on Moodle] slides [slideshow|print] - 07: Sep 20. Relations.

[read chapter 6, take quiz on Moodle] slides [slideshow|print] - 08: Sep 25. Functions (onto, composition).

[read chapter 7, take quiz on Moodle] slides [slideshow|print] - 09: Sep 27. Functions (one-to-one, bijection, monotonicity)

[read chapter 8, take quiz on Moodle] slides [slideshow|print] - 10: Oct 02. Counting. Mid-term 1 Review. Graphs

[review previous lectures, no Moodle quiz, but there will be clicker questions] slides [slideshow|print] - 11: Oct 04. Mid-term 1 Review. Graphs (continued).

[review previous lectures, no Moodle quiz, but there will be clicker questions] slides [slideshow|print] - --: Oct 09. First Midterm exam.
- 12: Oct 11. Graphs (continued).

[No pre-lecture preparation (recover from mid-term preparation!)] slides [slideshow|print] - 13: Oct 16. Graphs (ends). Induction.

[read chapters 9, 10 & sections 11.1 to 11.5, take quiz on Moodle] slides [slideshow|print] - 14: Oct 18. Induction (continued).

[read chapter 11. take quiz on Moodle] slides [slideshow|print] - 15: Oct 23. Recursive Definitions.

[read chapter 12. take quiz on Moodle] slides [slideshow|print] - 16: Oct 25. Trees.

[read sections 13.1 to 13.6. take quiz on Moodle] slides [slideshow|print] - 17: Oct 30. Trees.

[read chapter 13. take quiz on Moodle] slides [slideshow|print] - 18: Nov 1. Big O notation. Algorithms.

[read chapter 14 and sections 15.1-15.4. take quiz on Moodle] slides [slideshow|print] - 19: Nov 6. Algorithms

[read chapter 15. no pre-lecture quiz] slides [slideshow|print] - 20: Nov 8. P & NP. Review.

[chapter 16. no pre-lecture quiz] slides [slideshow|print] - --: Nov 13.
~~Second Midterm exam~~Fire alarm! - 21: Nov 15. P & NP, Proof by Contradiction, Sets of sets.

[chapters 16, 17 & sections 18.1-18.2. no pre-lecture quiz] slides [slideshow|print] - --: Nov 20. Thanksgiving break.
- --: Nov 22. Thanksgiving.
- 22: Nov 27. Sets of sets, Combinations.

[read chapter 18. take quiz on Moodle] [summary] - 23: Nov 29. State Diagrams.

[read chapter 19, take quiz on Moodle] [summary] - 24: Dec 4. State Diagrams.

[finish reading chapter 19, sections 20.1-20.4. take quiz on Moodle] slides [slideshow|print] - 25: Dec 6. Countability.

[read chapter 20. take quiz on Moodle] slides [slideshow|print] - 26: Dec 10. Uncountability and uncomputability. Wrap-up. (+ ICES forms.)

[chapter 20. no pre-lecture quiz.] slides [slideshow|print]