# Discrete Mathematics (Spring 2023)

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 rapidly learn mathematics.
• There exists a spectrum of reasoning between absolute mathematical formalism and informal reasoning, a spectrum that must be able to 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 in comfort in the study of mathematics itself as a discipline of modeling and problem solving.

## Schedule

Week 1: Introduction
T 01/24 Introduction to Python
Th 01/26 Typesetting with LaTeX Introduction to LaTeX
Week 2: Program Correctness
T 01/31 Propositions and Symbolic Execution Program Equivalence Proofs
Th 02/02 Preconditions and Proof States Assumptions in Proofs
Week 3: Induction
T 02/07 Inductive Reasoning List Induction Practice
Th 02/09 Mathematical Induction Mathematical Induction Practice
Week 4: Hoare Logic
T 02/14 Hoare Logic Exploring Hoare Logic
Th 02/16 (No class, snow day!)
Week 5: Program Verification
T 02/21 Compositional Reasoning (no reading)
W 02/23 Core Exam #1
Week 6: Logic and Sets
T 02/28 First-order Logic
Th 03/02 Introduction to Sets
T 03/07 Reasoning About Sets Reasoning with Sets
Th 03/09 Relations, Functions, and Equivalences
Week 8: Algorithmic Verification
T 03/14 Algorithmic Verification Introduction to Algorithmic Verification
Th 03/16 Algorithmic Verification (Cont.)
Spring Break: 3/18 to 4/3
Week 9: Graphs
T 04/04 Graphs and Their Variations Graph Problems
Th 04/06 Trees Spanning Trees
Week 10: Applications of Graphs
T 04/11 Minimum Spanning Trees Shortest Paths
Th 04/13 Core Exam #2
Week 11: Combinatorial Reasoning
T 04/18 Fundamental Counting Principles Counting Practice
Th 04/20 Ordered and Unordered Choice More Counting Practice
Week 12: Probability Theory
T 04/25 Counting-based Reasoning Combinatorial Walkthrough
Th 04/27 Frequentist Probability Probability Practice
Week 13: Probability
T 05/02 Random Variables and Expectation Working with Expectation
Th 05/04 Conditional Probability Inference
Week 14: Statistical Reasoning
T 05/09 Core Exam #3
Th 05/11 The End of the Line
Finals week: 05/16 to 5/19
F 05/19 All remaining work due (5 PM CST)