CSC 208: Discrete Mathematics

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

Date	Topic/Reading	Lab
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
Week 7: Reasoning About 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)

CSC 208-01

Discrete Mathematics (Spring 2023)

Schedule