About
Syllabus
Course Tools
Lab Solutions
Week 1: Program Reasoning
Demonstration Exercise #1
9/2: Introduction to Python and LaTeX
Course Tools
9/4: A Review of Concrete Evaluation
Concrete Evaluation
Lab: Exploring Python
9/6: Symbolically Executing Programs
Proposition and Proofs
Symbolic Execution
Lab: Program Equivalence Proofs
Week 2: Inductive Reasoning
Demonstration Exercise #2
9/9: Assumptions and the Nature of Proof
Preconditions and Proof States
Lab: Assumptions in Proofs
9/11: Structural Induction
Inductive Reasoning Over Lists
Lab: Recursion to Induction
9/13: Induction with Numbers
Mathematical Induction
Lab: Mathematical Induction Practice
Week 3: Logic
Demonstration Exercise #3
9/16: Variants of Induction
Variants of Inductive Proof
Lab: Strong Induction
9/17: Logic
Propositional Logic
First-order Logic
Lab: Modeling with Logic
9/19: Logical Reasoning
Natural Deduction
Lab: Logical Reasoning
Week 4: Logic Wrap-up
9/23: Natural Deduction (cont.)
Natural Deduction (review)
Lab: More Logical Reasoning
9/25: Logic Wrap-up
Additional Topics in Logic
Lab: Beyond Program Correctness
9/27: Exam #1
Week 5: Mathematically Modeling Data
Demonstration Exercise #4
9/30: Introduction to Sets
Sets and Their Operations
Set Inclusion Principles
10/2: Proving Set Equality
Lab: Artificial Examples and Sets
10/4: Proof By Contradiction
Contradictory Proof
Week 6: Mathematically Modeling Behavior
Demonstration Exercise #5
10/7: Relations and Functions
Functions and Relations
10/9: The Ontology of Functions
Lab: A Plethora of Definitions
10/11: Equivalences and Orderings
Equivalences
Week 7: Graphs
Demonstration Exercise #6
10/14: Modeling with Graphs
Introduction to Graphs
10/16: Exploring Graph Problems
Lab: Exploring Graph Problems
10/18: Shortest Paths
Minimum Spannning Trees
Shortest Paths
Lab: Spanning Trees and Shortest Paths
(Fall break: 10/21–10/25)
Week 8: Case Study: Finite Automata
12/2: Finite Automata
Case Study: Automata
12/4: Modeling with Automata
Lab: Verification of State Machines
11/1: Exam #2
Week 9: Counting
Demonstration Exercise #7
11/4: Fundamental Counting Principles
Fundamental Counting Principles
Ordered and Unordered Choice
11/6: Strategies for Counting
Lab: Counting Practice
11/8: Double Inclusion
Counting-based Reasoning
Week 10: Complexity
11/11: Counting Wrap-up
Lab: Case Study: Derangements
11/13: Counting Operations
Counting Operations
Graph Complexity
11/15: Recurrence Relations
Recurrences
Lab: Recurrences
Week 11: Probability
Demonstration Exercise #8
11/18: Frequentist Probability
Frequentist Probability
Random Variables and Expectation
11/20: Probability Lab
Lab: Probability Practice
11/22: Conditional Probabilities
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
(No Reading or lab!)
12/4: Probabilistic Inference
(No Reading!)
Lab: Inference
12/6: Exam #3
Week 14: Case Study: The Limits of Computation
12/9: Infinite Sets and Countability
Counting
Lab: Countability Proofs
12/11: The Thrilling Conclusion
(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
Light
Rust
Coal
Navy
Ayu
CSC 208: Discrete Structures
Counting
Our reading on countability can be found on Profs. Autry's and Liu's CSC 208 website:
Counting (CSC 208 (24sp))