CS 1800 (Discrete Math) Schedule

CS 1800: Discrete Math
Schedule for Summer 2025

This schedule is always subject to change.

Note: This semester we will not cover section 6 of our Resources page [Relations and functions].

Week 1
May 5-11
- Propositions, if-then statements, and straightforward proofs (Resources: section 2)
- Sets (Resources: section 3)
- Non-constructive existence proofs (Resources: 4D)
- Proof by contrapositive, by contradiction, and by smallest counterexample (Resources: 4A)
- Pigeonhole principle (Resources: 4C)
- Homework 1 due on Saturday, May 10
Week 2
May 12-18
- Homework 2 due on Tuesday, May 13
- Logic (Resources: section 5) [Last Exam 1 topic]
- Homework 3 due on Thursday, May 15
- Proof by induction (Resources: 4B) [First Exam 2 topic]
Week 3
May 19-25
- Exam 1 on Monday, May 19, 6pm. Duration 75 minutes. Exam 1 covers Week 1 and Logic.
- Summations (Resources: 10)
- Big-O notation; exaggerating and simplifying (Resources: 7)
- Recurrence relations using big-O (Resources: 8)
- Homework 4 due on Friday, May 23
- Homework 5 due on Sunday, May 25
Week 4
May 26 - June 1
- Homework 6 due on Tuesday, May 27
- Graphs: intro (Resources: 9A)
- Cliques, Independent sets, Ramsey numbers (Resources: 9B)
- Connectivity and trees (Resources: 9C)
- Minimum Spanning Trees (MST) (Resources: 9D)
- Exam 2 on Friday, May 30, 6pm. Duration 75 minutes, covering Induction and Week 3.
Week 5
June 2-8
- Planarity (Resources: 9E)
- Vertex coloring (Resources: 9F) [Last Exam 3 topic]
- Homework 7 due on Wednesday, June 4
- Homework 8 due on Friday, June 6
- Homework 9 due on Sunday, June 8
- Combinatorics (Resources: 11) [First Exam 4 topic]
Week 6
June 9-15
- Exam 3 on Wednesday, June 11, 6pm. Duration 75 minutes, covering Graphs (Week 4 and part of Week 5).
- Probability intro (Resources: 12A)
- Conditional probability (Resources: 12B)
- Random variables (Resources: 12C)
- Indicator random variables (IRV) (Resources: 12D)
- Homework 10 due on Sunday, June 15
Week 7 (half-week, officially)
June 16-18
- Homework 11 due on Tuesday, June 17
- Homework 12 due on Thursday, June 19
Week 8
June 23
- Exam 4 on Monday, June 23, 6pm. Duration 75 minutes, covering Combinatorics and Week 6.