About
Syllabus
Course Tools
Lab Solutions
Week 1: Program Reasoning
Demonstration Exercise #1
9/2: Introduction to Python and LaTeX
1. Course Tools
9/4: A Review of Concrete Evaluation
1. Concrete Evaluation
2. Lab: Exploring Python
9/6: Symbolically Executing Programs
Week 2: Inductive Reasoning
Demonstration Exercise #2
9/9: Assumptions and the Nature of Proof
1. Preconditions and Proof States
2. Lab: Assumptions in Proofs
9/11: Structural Induction
1. Inductive Reasoning Over Lists
2. Lab: Recursion to Induction
9/13: Induction with Numbers
1. Mathematical Induction
2. Lab: Mathematical Induction Practice
Week 3: Logic
Demonstration Exercise #3
9/16: Variants of Induction
1. Variants of Inductive Proof
2. Lab: Strong Induction
9/17: Logic
9/19: Logical Reasoning
1. Natural Deduction
2. Lab: Logical Reasoning
Week 4: Logic Wrap-up
9/23: Natural Deduction (cont.)
1. Natural Deduction (review)
2. Lab: More Logical Reasoning
9/25: Logic Wrap-up
1. Additional Topics in Logic
2. Lab: Beyond Program Correctness
9/27: Exam #1
Week 5: Mathematically Modeling Data
Demonstration Exercise #4
9/30: Introduction to Sets
1. Sets and Their Operations
2. Set Inclusion Principles
10/2: Proving Set Equality
1. Lab: Artificial Examples and Sets
10/4: Proof By Contradiction
1. Contradictory Proof
Week 6: Mathematically Modeling Behavior
Demonstration Exercise #5
10/7: Relations and Functions
1. Functions and Relations
10/9: The Ontology of Functions
1. Lab: A Plethora of Definitions
10/11: Equivalences and Orderings
1. Equivalences
Week 7: Graphs
Demonstration Exercise #6
10/14: Modeling with Graphs
1. Introduction to Graphs
10/16: Exploring Graph Problems
1. Lab: Exploring Graph Problems
10/18: Shortest Paths
(Fall break: 10/21–10/25)
Week 8: Case Study: Finite Automata
12/2: Finite Automata
1. Case Study: Automata
12/4: Modeling with Automata
1. Lab: Verification of State Machines
11/1: Exam #2
Week 9: Counting
Demonstration Exercise #7
11/4: Fundamental Counting Principles
1. Fundamental Counting Principles
2. Ordered and Unordered Choice
11/6: Strategies for Counting
1. Lab: Counting Practice
11/8: Double Inclusion
1. Counting-based Reasoning
Week 10: Complexity
11/11: Counting Wrap-up
1. Lab: Case Study: Derangements
11/13: Counting Operations
1. Counting Operations
2. Graph Complexity
11/15: Recurrence Relations
1. Recurrences
2. Lab: Recurrences
Week 11: Probability
Demonstration Exercise #8
11/18: Frequentist Probability
1. Frequentist Probability
2. Random Variables and Expectation
11/20: Probability Lab
1. Lab: Probability Practice
11/22: Conditional Probabilities
1. Conditional Probabilities
Week 12: Make-up Week
11/25: Make-up Exam
11/27: No class!
(Thanksgiving break: 11/28–11/29)
Week 13: Case Study: Probabilistic Reasoning
12/2: Markov Chains
1. (No Reading or lab!)
12/4: Probabilistic Inference
1. (No Reading!)
2. Lab: Inference
12/6: Exam #3
Week 14: Case Study: The Limits of Computation
12/9: Infinite Sets and Countability
1. Counting
2. Lab: Countability Proofs
12/11: The Thrilling Conclusion
1. (No Reading!)
12/13: Guest Lecturer: TBD
(Finals week: 12/16–12/22)
12/18 (2–5 PM): Revision Exam #4
12/20 5 PM: All work due deadline

Lab: Countability Proofs

Our lab on countability proofs can be found on Profs. Autry's and Liu's CSC 208 website:

Countability Proofs (CSC 208 (24sp))

CSC 208: Discrete Structures

Lab: Countability Proofs