The following gives a day-by-day breakdown of topics covered, readings assigned, and assignment handsouts/due dates. Each topic includes several required readings that students should read before the topic is discussed in class – always look ahead a few days to see what readings you should be doing. Some topics also have supplemental (non-required) readings that students can look into if they want to delve more deeply into that topic.
The schedule in this class is flexible, and past dates will be updated to reflect what was actually covered. Future dates are always tentative and subject to change.
Topics: Syllabus review, class overview, and LaTeX
Handout: Syllabus
Assigned: Assignment 0
Due: Assignment 0
Reading: Textbook, Chapter 1
Topics: Basic proof techniques and logical reasoning
Topics: Continued from last time…
Assigned: Assignment 1
Reading: Textbook, Chapters 3 and 5
Topics: Logical formulas and the SAT problem; Induction basics
Reading: Textbook, Sections 6.1–6.3
Topics: Induction examples; Introduction to States, invariants, and program correctness/termination proofs
Due: Assignment 1
Topics: Finish: Introduction to States, invariants, and program correctness/termination proofs Assigned: Assignment 2
Reading: Textbook, Sections 7.1–7.4
Topics: Recursive data types
Reading: Textbook, Chapter 14
Topics: Sums and Asymptotics
Reading: Textbook, Sections 8.1–8.2
Topics: Infinite cardinality and the halting problem
Due: Assignment 2
Reading: Textbook, Chapter 22
Topics: Recurrences
Topics: Review for midterm exam 1
Topics: Midterm exam 1
I will try to keep a tentative schedule filled out with planned topics for the next 2–3 weeks. Beyond that, there’s too much uncertainty, but the general outline of the course will be one-third analysis/proof techniques; one-third graph theory; and one-third probabilistic analysis.
Friday, December 6, 3:30-6:00