CSC/MAT 208

Discrete Structures (Spring 2024)

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:

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 Homework
Week 1: Introduction
T 01/23 Welcome! (slides-introduction ) Introduction to LaTeX
Th 01/25 Concrete Evaluation (slides-ceval ) Program Equivalence Proofs
Week 2: Program Correctness
T 01/30 Propositions and Symbolic Execution (slides-pse ) Program Equivalence Proofs-Extended
Th 02/01 Preconditions and Proof States (slides-pps ) Assumptions in Proofs homework1
Week 3: Intro to Induction
T 02/06 Inductive Reasoning (slides-ir ) List Induction Practice
Th 02/08 Mathematical Induction List Induction Practice - Extended homework2
Week 4: Induction Practice
T 02/13 Continuing on Induction Mathematical Induction Practice
Th 02/15 Hoare Logic Part 1 (slides-hl-1 ) Mathematical Induction Practice - Extended
Week 5: Hoare Logic
T 02/20 Hoare Logic Part 1 (practice) Exploring Hoare Logic
Th 02/22 Hoare Logic Part 2 (slides-hl-2 ) Loop Invariant and Exam Review
Week 6: Formal Logic
T 02/27 First Order Logic (slides-fol ) Negation and Implication
Th 02/29 Natural Deduction (slides-nd ) Propositional Proofs
Week 7: Reasoning About Sets
T 03/05 Sets and Their Operations Reasoning with Sets
Th 03/07 Set Inclusion Set Inclusion Proofs
Week 8: Algorithmic Verification
Spring Break!
Week 9: Graphs
Week 10: Applications of Graphs
Week 11: Combinatorial Reasoning
Week 12: Probability Theory
Week 13: Probability
Week 14: Statistical Reasoning
Finals week!
F 05/17 All remaining work due (5 PM CST)