The following gives a day-by-day breakdown of topics covered, readings assigned, and assignment handouts/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.2
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
Topics: Catch-up day and solution review
Due: Assignment 2
Topics: Problem solving/presentation/practice day
Topics: Review for midterm exam 1
Topics: Midterm exam 1
Reading: Textbook, Chapter 22
Topics: Midterm discussion; Recurrences
Assigned: Practice Problems 3a and Assignment 3
Topics: Finish recurrences
Reading: Textbook, Sections 10.1–10.6
Topics: Directed graphs, dependencies, and scheduling
Assigned: Practice Problems 3b
Due: Practice Problems 3b
Reading: Textbook, Sections 12.1–12.3
Topics: Finish digraphs, and then simple graph definitions/common graphs
Assigned: Practice Problems 4a
Due: Solo Assignment 3
Reading: Textbook, Section 12.4
Topics: Graph isomorphism
Assigned: Solo Assignment 4
Due: Practice Problems 4a
Reading: Textbook, Section 12.5
Topics: Bipartite Graphs, Matching, and Hall’s Theorem
Assigned: Practice Problems 4b
Reading: Textbook, Section 12.6
Topics: Graph coloring and applications
Due: Practice Problems 4b
Reading: Textbook, Section 12.7–12.10
Topics: Graph connectivity and special walks/tours
Due: Solo Assignment 4
Topics: Midterm exam 2 review day
Topics: Midterm exam 2
Reading: Textbook, Section 17.1–17.4
Topics: Discuss midterm 2; final coloring notes; start probability
Assigned: Practice Problem 5a
Due: Practice Problems 5a
Reading: Textbook, Section 18.1–18.5
Topics: More probability and conditional probability
Assigned: Practice Problems 5b
Reading: Textbook, Section 19.1–19.5
Topics: Random variables, distribution functions, and expectation
Assigned: Solo Assignment 5
Due: Practice Problems 5b
Topics: Random variables – day 2
Topics: Probabilistic algorithms and recurrences
Due: Solo Assignment 5
Topics: Last day of class – review
Friday, December 6, 3:30-6:00