Discrete Structures

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.

Date Topic/Reading Lab Deliverables
Week 0: Introduction
F 8/30 Introduction
Week 1: Program Reasoning
M 9/2 Introduction to Python and LaTeX Python and LaTeX practice Demonstration Exercise #1
W 9/4 Propositions and Symbolic Execution
F 9/6 Preconditions and Proof States
Week 2: Inductive Reasoning
M 9/9 Inductive Reasoning Demonstration Exercise #2
W 9/11 Mathematical Induction
F 9/13 Variants of Inductive Reasoning
Week 3: Logic
M 9/16 Propositional Logic Demonstration Exercise #3
W 9/18 Natural Deduction
F 9/20 Quantification
Week 4: Case Study: Imperative Reasoning
M 9/23 Pre- and Post-condition Reasoning
W 9/25 Loop Invariants
F 9/27 Exam #1
Week 5: Mathematically Modeling Data
M 9/30 Set Operations Demonstration Exercise #4
W 10/2 Set Inclusion and Equality
F 10/4 Modeling with Math
Week 6: Mathematically Modeling Behavior
M 10/7 Relations and Functions Demonstration Exercise #5
W 10/9 The Ontology of Functions
F 10/11 Equivalences and Orderings
Week 7: Graphs
M 10/14 Modeling with Graphs Demonstration Exercise #7
W 10/16 Properties of Graphs
F 10/18 Survey of Graph Problems
Fall break
Week 8: Case Study: Graph Algorithms
M 10/28 Spanning Trees
W 10/30 Shortest Paths
F 11/1 Exam #2
Week 9: Counting
M 11/4 Fundamental Counting Principles Demonstration Exercise #8
W 11/6 Strategies for Counting
F 11/8 Double Inclusion
Week 10: Complexity
M 11/11 Counting Operations Demonstration Exercise #9
W 11/13 Asymptotic Analysis
F 11/15 Recurrence Relations
Week 11: Probability
M 11/18 Frequentist Probability Demonstration Exercise #10
W 11/20 Probability Distributions
F 11/22 Conditional Probability
Week 12: Statistical Learning
M 11/25 Case Study: Bayesian Inference Demonstration Exercise #11
W 11/27 (No class, Thanksgiving travel!)
Thanksgiving break: 11/28–11/29
Week 13: Case Study: Automata
M 12/2 Finite Automata
W 12/4 Modeling with Automata
F 12/6 Exam #3
Week 14: Case Study: The Limits of Computation
M 12/9 Markov Chains
W 12/11 Infinite Sets and Countability
F 12/13 The Thrilling Conclusion
Finals week: 12/16–12/20