CS 173: Discrete Structures Schedule


A typical weekly schedule in this course will be as follows.

Solutions for lecture worksheets and homeworks will be graded for participation. They are meant to encourage you to solve problems which is the best way to learn the material in this course. The examlet problems will be variants of the problems seen in the lecture worksheet and homeworks.

 

Video recordings of lecture materials can be accessed from the CS 173 channel on Mediaspace. Graded work will be turned in on PrairieLearn. Zoom links for lecture meetings on Thursday and August 25 (Tuesday) can be found on our Zoom links page.

In the table below, sections and chapters refer to portions of the class textbook Mathematics for Computer Science. Topics covered in the lecture can often also be found in the alternate textbook for the course Building Blocks for Theoretical Computer Science.

Week Date Lecture/Test Topic Reference Material
1
Aug 25 Course Overview and Administrivia Syllabus
  Aug 27 Propositional and Predicate Logic
[notes, worksheet, worksheet solutions]
Video lecture: Logic (backup)
Optional video: P versus NP (backup)
Textbook: Chapter 3
  Aug 27 Week 1 worksheet due  
  Aug 29 Homework 1 due
Homework 1 solutions
Optional video: Problem Demo [Notes]
2
Sep 01 No class  
  Sep 03 Proofs
[notes, worksheet, worksheet solutions]
Video lecture: Proofs
Optional video: Why prove?
Textbook: Chapter 1
  Sep 03 Week 2 worksheet due Read Exam instructions:
Student Instructions, How to position your phone
  Sep 05

Homework 2 due
Homework 2 solutions

Optional video: Bad Proof Demo (backup) [Notes]
Optional video: Good Proof Demo (backup) [Notes]
3
Sep 08 Examlet 1 on Logic and Proofs Skill set
  Sep 10 Sets, Functions, and Relations
[notes, worksheet, worksheet solutions]
Video lecture: Sets and Functions
Textbook: Chapter 4
  Sep 10 Week 3 worksheet due  
  Sep 12 Homework 3 due
Homework 3 solutions
Optional Video: Problem Demo (backup) [Notes]
4
Sep 15 Examlet 2 on Sets, functions, and relations Skill set
  Sep 17 Cardinality of sets
[notes, worksheet, worksheet solutions]
Video Lecture: Cardinality
Optional video: Computability
Textbook: Chapter 8 and Section 4.5
  Sep 17 Week 4 worksheet due  
  Sep 19 Homework 4 due
Homework 4 solutions
Video: Problem Demo #1 [Notes]
Video: Problem Demo #2 [Notes]
5
Sep 22 Examlet 3 on Cardinality Skill set
  Sep 24 Directed Graphs
[notes, worksheetworksheet solutions]
Video Lecture: Directed Graphs
Textbook: Chapter 10 (skip 10.3,
10.5.2, 10.7-10.9, 10.10.1)
  Sep 24 Week 5 worksheet due  
  Sep 26 Homework 5 due
Homework 5 solutions
Video: Problem Demo #1 and #2 [Notes]
6
Sep 29 Examlet 4 on Directed graphs Skill set
  Oct 01 Simple Graphs and Trees
[notesworksheetworksheet solutions]
Video Lecture: Simple Graphs and Trees (backup)
Textbook: Chapter 12
  Oct 01 Week 6 worksheet due  
  Oct 03 Homework 6 due
Homework 6 solutions
Videos: Problem Demo [Notes]
Graph MC/ProofBlocks Demo
7
Oct 06 Examlet 5 on Undirected Graphs and trees Skill set
  Oct 08 Induction
[notesworksheetworksheet solutions]
Video Lecture: Induction
Textbook: Chapter 5, 6-6.2
  Oct 08 Week 7 worksheet due  
  Oct 10 Homework 7 due
Homework 7 solutions
Video: Problem Demos #1 (backup) and #2 (backup) [Notes]
8
Oct 13 Examlet 6 on Induction Skill set
  Oct 15 Recursively defined sets and Structural Induction
[notes, worksheetworksheet solutions]
Video Lecture
Textbook: Chapter 7
  Oct 15 Week 8 worksheet due  
  Oct 17 Homework 8 due
Homework 8 solutions
 
9
Oct 20 Examlet 7 on Recursively defined sets and Structural Induction Skill set
  Oct 22 Number Theory
[notes, worksheet, worksheet solutions]
Video Lecture: Number Theory
Textbook: Chapter 9
  Oct 22 Week 9 worksheet due  
  Oct 24 Homework 9 due
Homework 9 solutions
Video: Problem Demo #1 [Notes] and #2 [Notes
10
Oct 27 Examlet 8 on Number Theory Skill set
  Oct 29 Counting
[notes, worksheet, worksheet solutions]
Video Lecture: Counting
Textbook: Chapter 15
  Oct 29 Week 10 worksheet due  
  Oct 31 ðŸÅ½ƒ Homework 10 due
Homework 10 solutions
Video: Problem Demo #1 [Notes] and #2 [Notes]
11
Nov 03 Examlet 9 on Counting CANCEL(L)ED Election Day (all-campus holiday)
  Nov 05 Probability
[notes, worksheet, worksheet solutions]
Video Lecture: Probability
Textbook: Chapter 17
  Nov 05 Week 11 worksheet due  
  Nov 07 Homework 11 due
Homework 11 solutions
Video: Problem Demo [Notes]
12
Nov 10 Examlet 10 on Probability and Counting Skill set
  Nov 12 Summing series and solving recurrences
[notes, worksheet, worksheet solutions]
Video Lecture #1 and #2
Textbook: Chapter 14/22
  Nov 12 Week 12 worksheet due  
  Nov 14 Homework 12 due
Homework 12 solutions
Video: Problem Demo #1 [Notes] and #2 [Notes]
13
Nov 17 Examlet 11 on Summing series and solving recurrences Skill set
  Nov 19 Algorithm analysis and Big O
[notesworksheetworksheet solutions]
Video Lecture: Big O
Textbook: Chapter 14.7
  Nov 19 Week 13 worksheet due  
--
Nov 21 to Nov 29 Thanksgiving Break   
14
Dec 01 Homework 13 due (No test or class)
Homework 13 solutions
 
  Dec 03 Pigeon Hole Principle (PHP) and
Principle of Inclusion-Exclusion (PIE)
[notes, worksheet, worksheet solutions]
Video Lecture: PHP and PIE
Textbook: Sections 15.8 and 15.9
  Dec 03 Week 14 worksheet due  
  Dec 05 Homework 14 due
Homework 14 solutions
 
15
Dec 08 Examlet 12 on Algorithm analysis and Big O, PHP, and PIE Skill set
--
Dec 11 (conflict)
Dec 14
Final Exam: Retake up to 3 examlets again