CSC 208-01

Discrete Mathematics (Fall 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:

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 Deliverables
Week 0: Welcome Back!
F 08/25 Welcome Back!
Week 1: Introduction
M 08/28 Introduction to LaTeX
W 08/30 Concrete Evaluation Program Equivalence Proofs
F 09/01 Propositions and Symbolic Execution Program Equivalence Proofs
Week 2: Program Correctness
M 09/04 Preconditions and Proof States Assumptions in Proofs
W 09/06 Assumptions in Proofs (continued) Assumptions in Proofs
F 09/08 Inductive Reasoning List Induction Practice
Week 3: Induction
M 09/11 More List Induction List Induction Practice
W 09/13 Mathematical Induction Mathematical Induction Practice
F 09/15 More Mathematical Induction demo 1
Week 4: Continuing Induction
M 09/18 Even More Mathematical Induction Mathematical Induction Practice
W 09/20 Mathematical Induction and Other Variations Introducing Hoare Logic
F 09/22 Hoare Logic Part 1 Exploring Hoare Logic
Week 5: Impure Programs
M 09/25 More Hoare Exploring Hoare Logic
W 09/27 Hoare Logic Part 2 demo 2
F 09/29 Exam Review exam 1
Week 6: Logic and Sets
M 10/02 First-order Logic Exploring Logic
W 10/04 Natural Deduction Rules of Logic
F 10/06 Sets and their Operations Exploring Sets
Week 7: Reasoning About Sets
M 10/09 Set Inclusion Reasoning with Sets
W 10/11 More Sets Reasoning with Sets
F 10/13 And still more Sets demo-3
Fall Break!
Week 8: Functions and Countability
M 10/23 Relations, Functions, and Equivalences Relations and Functions
W 10/25 More Functions Relations and Functions
F 10/27 Counting Sets demo-4
Week 9: Graph Introduction
M 10/30 Contradiction, Cantor, and Countability Uncountable Sets
W 11/01 Graphs and Their Variations Graph Problems
F 11/03 Graph Practice Graph Practice
Week 10: Graphs and Trees
M 11/06 More Graphs Graph Practice
W 11/08 Trees Tree Practice
F 11/10 Exam Review exam 2
Week 11: Combinatorial Reasoning
M 11/13 Fundamental Counting Principles Counting Practice
W 11/15 Ordered and Unordered Choice More Counting Practice
F 11/17 Continued Counting More Counting Practice
Week 12: Counting
M 11/20 Counting-based Reasoning Combinatorial Walkthrough
W 11/22 Wrapping up Counting Combinatorial Walkthrough
F 11/24 Thanksgiving Break! Thanksgiving Break!
Week 13: Probability
M 11/27 Frequentist Probability Probability Practice
W 11/29 Random Variables and Expectation Working with Expectation
F 12/01 Random Practice Working with Expectation
Week 14: Statistical Reasoning
M 12/04 Conditional Probability Inference
W 12/06 Exam Review
F 12/08 The End of the Line
Finals week: 12/12 to 12/15
M 12/11 No class
W 12/13 No class
F 12/15 All remaining work due (5 PM CST)
-----------------------------------------------------
Everything below is from an old version, disregard...
-----------------------------------------------------
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)