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

CSC 208: Discrete Mathematics (Fall 2024)

Instructor: Peter-Michael Osera
Office Hours: Science 2811, by appointment
Course Mentor: Peter Versh
Meeting Times: MWF 3:00–3:50, Science 3815

What are the mathematical foundations of computer science? How does mathematical formalism relate to the pragmatics of computer science? In this course, we study discrete mathematics, broadly the branches of mathematics that study discrete objects, and their applications towards computer science.

By understanding discrete mathematics deeply, we, in turn, gain an understanding of how mathematics informs our studies as computer scientists, namely:

We solve problems in computer science by modeling domains of problems, a process that is, at its core, mathematical.
The interpretation of the syntax and semantics of mathematics is identical to the interpretation of a programming language, so we can leverage our understanding of programming to learn mathematics rapidly.
There is a spectrum of reasoning between absolute mathematical formalism and informal reasoning, a spectrum that we must move across at will as competent programmers.

Finally, by studying discrete mathematics in depth and relating it to our experiences as computer programmers, we also gain expertise and comfort in studying mathematics as a discipline of modeling and problem-solving.