CSE 311: Foundations of Computing I, Spring 2023

Schedule

For future lectures, this is a tentative schedule. The exact contents are subject to change. Links to future materials may also be broken.

Week 1
Topic
Week 1
Lecture 1
(Mon, Mar 27)
Propositional Logic
slides annotated (A) annotated (B)
Related: Rosen 1.1
Lecture 2
(Wed, Mar 29)
Equivalences
slides annotated (A) annotated (B)
Related: Rosen 1.3 HW1 Out
Section 1
(Thu, Mar 30)
Propositional Logic & Equivalences
materials solutions
Lecture 3
(Fri, Mar 31)
Circuits
slides annotated (A) annotated (B)
Related: Rosen 12.3
Week 2
Lecture 4
(Mon, Apr 3)
Boolean algebra, Canonical Forms
slides annotated (A) annotated (B)
Related: Rosen 12.1
Lecture 5
(Wed, Apr 5)
Canonical Forms, Predicate Logic
slides annotated (A) annotated (B)
Related: Rosen 1.4-1.5 HW2 Out HW1 Due
Section 2
(Thu, Apr 6)
Circuits & Predicate Logic
materials solutions
Lecture 6
(Fri, Apr 7)
Predicate Logic, Inference
slides annotated (A) annotated (B)
Related: Rosen 1.6
Week 3
Lecture 7
(Mon, Apr 10)
Propositional & Predicate Logic Proofs
slides annotated (A) annotated (B)
Related: Rosen 1.6-1.7
Lecture 8
(Wed, Apr 12)
Predicate Logic Proofs, English Proofs
slides annotated (A) annotated (B)
Related: Rosen 1.7-1.8 HW3 Out HW2 Due
Section 3
(Thu, Apr 13)
Predicate Logic, Proofs
materials solutions
Lecture 9
(Fri, Apr 14)
English Proof Strategies, Number Theory
slides annotated (A) annotated (B)
Related: Rosen 1.8, 4.1
Week 4
Lecture 10
(Mon, Apr 17)
Modular Arithmetic
slides annotated (A) annotated (B)
Related: Rosen 4.1
Lecture 11
(Wed, Apr 19)
Applications of Modular Arithmetic, Prime Factorization, GCD
slides annotated (A) annotated (B)
Related: Rosen 4.3 HW4 Out HW3 Due
Section 4
(Thurs, Apr 20)
Number Theory
materials solutions
Lecture 12
(Fri, Apr 21)
Modular Equations, Exponentiation, Set Theory
slides annotated (A) annotated (B)
Related: Rosen 4.4.2, 4.2.4, 2.1
Week 5
Lecture 13
(Mon, Apr 24)
Set Theory
slides annotated (A) annotated (B)
Related: Rosen 2.1-2.2
Lecture 14
(Wed, Apr 26)
Induction
slides annotated (A) annotated (B)
Related: Rosen 5.1 HW5 Out HW4 Due
Section 5
(Thu, Apr 27)
Modular Exponentiation, Set Theory, Induction
materials solutions
Lecture 15
(Fri, Apr 28)
Strong Induction and Recursion
slides annotated (A) annotated (B)
Related: Rosen 5.2-5.3
Week 6
Lecture 16
(Mon, May 1)
Recursively Defined Sets and Structural Induction
slides annotated (A) annotated (B)
Related: Rosen 5.3
Lecture 17
(Wed, May 3)
More Structural Induction
slides annotated (A) annotated (B)
Related: Rosen 5.3 HW5 Due
Section 6
(Thu, May 4)
Induction: Ordinary, Strong, Structural
materials solutions
Lecture 18
(Fri, May 5)
Strings and Regular Expressions
slides annotated (A) annotated (B)
Related: Rosen 13.4.1
Week 7
Lecture 19
(Mon, May 8)
Context-Free Grammars (CFGs)
slides annotated (A) annotated (B)
Related: Rosen 13.1.4
Midterm
(Wed, May 10)
Midterm
HW6 Out
Section 7
(Thurs, May 11)
Induction, Regular Expressions
materials solutions
Lecture 20
(Fri, May 12)
CFGs and Relations
slides annotated (A) annotated (B)
Related: Rosen 13.1.4,9.1,9.3
Week 8
Lecture 21
(Mon, May 15)
Directed Graphs, Finite State Machines (FSMs)
slides annotated (A) annotated (B)
Related: Rosen 9.1,9.3
Lecture 22
(Wed, May 17)
Finite State Machine Design
slides annotated (A) annotated (B)
HW7 Out HW6 Due
Section 8
(Thurs, May 18)
CFGs, Relations, Finite State Machines
materials solutions
Lecture 23
(Fri, May 19)
Minimization, NFAs
slides annotated (A) annotated (B)
Week 9
Lecture 24
(Mon, May 22)
NFAs, RegExp, NFAs to DFAs
slides annotated (A) annotated (B)
Lecture 25
(Wed, May 24)
The Limitations of DFA/NFA/RegExp
slides annotated (A) annotated (B)
HW8 Out HW7 Due
Section 9
(Thurs, May 25)
FSM Minimization, NFAs, Subset Construction, Irregularity
materials solutions
Lecture 26
(Fri, May 26)
Cardinality, Uncomputability
slides annotated (A) annotated (B)
Week 10
(Mon, May 29)
No Lecture: Memorial Day
Lecture 27
(Wed, May 31)
Undecidability of the Halting Problem
slides annotated (A) annotated (B)
Section 10
(Thu, Jun 1)
Review
materials solutions
Lecture 28
(Fri, Jun 2)
Turing Machines and Reductions
slides annotated (A) annotated (B)
HW8 Due
Exam Week
Final Exam
(Mon, Jun 5)
Final exams are scheduled at 2:30-4:20 pm and 4:30-6:20 pm in JHN 102 rather than our regular classroom.
(You will need to select one of these two times to take your exam and confirm your choice by Saturday June 3.)

This course website heavily follows the example of the website of CSE373 2019 Spring.