# CSE 311: Foundations of Computing I

## Announcements

• 01/27
Additional LaTeX resources (including a homework template!!!) can be found on the Resources page.
• 01/04
Welcome to CSE 311! This is our course website — cs.uw.edu/311. Most of the materials in this class will be posted here. Visit early and often!
• 12/30

## Calendar

Week 1
Topic
Materials
Assignments
Week 1
Lecture 1
(Mon 01/04)
Welcome! Propositional Logic
Lecture 2
(Wed 01/06)
Equivalences, Proofs
Homework 1 released, pdf
Section 1
(Thu 01/07)
Propostions, Translation
Lecture 3
(Fri 01/08)
Proofs, Contrapositives, Digital Logic
Week 2
Lecture 4
(Mon 01/11)
Digital logic and Boolean Algebra
Lecture 5
(Wed 01/13)
Normal forms, quantifiers, and predicates
Section 2
(Thu 01/14)
Digital Logic, Equivalence Proofs
Lecture 6
(Fri 01/15)
Quantifiers and Negations
• Slides pdf
• Activity pdf
• Additional slides from ``extra” lecture pdf
Homework 2 released, pdf
Week 3
Martin Luther King Day, No class.
(Mon 01/18)
Lecture 7
(Wed 01/20)
Proofs!
Section 3
(Thu 01/21)
Quantifiers, Proofs
Lecture 8
(Fri 01/22)
Inference Rules and Proofs with Quantifiers
Week 4
Lecture 9
(Mon 01/25)
Inference proofs with quantifiers and English proofs
Lecture 10
(Wed 01/27)
Sets!
• Slides: pdf
• Activity: None this day
Section 4
(Thu 01/28)
Lecture 11
(Fri 01/29)
Number Theory
• Slides: pdf
• Annotated Slides: pdf
• Activity: pdf
Homework 4 released, pdf
Week 5
Lecture 12
(Mon 02/01)
More Number Theory, Primes and GCD
Lecture 13
(Wed 02/03)
GCD and more Number Theory Proofs
Section 5
(Thu 02/04)
Lecture 14
(Fri 02/05)
Homework 5 released, pdf
Week 6
Lecture 15
(Mon 02/08)
Induction and Strong Induction
Lecture 16
(Wed 02/10)
Even More Induction
• Slides: pdf
• Annotated Slides: pdf
• Activity: pdf
Section 6
(Thu 02/11)
Review for Midterm
Lecture 17
(Fri 02/12)
Structural Induction
Week 7
President’s Day, No Class
(Mon 02/15)
Exam, No Class
(Wed 02/17)
Section 7
(Thu 02/18)
Cancelled, Exam
Lecture 18
(Fri 02/19)
Regular Expressions
Week 8
Lecture 19
(Mon 02/22)
Context-Free Grammars
• Slides: pdf
• Activity: pdf
• Annotated: pdf
• Homework, released Tuesday: pdf
Lecture 20
(Wed 02/24)
Relations and Graphs
Section 8
(Thu 02/25)
Structural Induction, CFG’s, RegEx’s
Lecture 21
(Fri 02/26)
Relations and Graphs
Week 9
Lecture 22
(Mon 03/01)
Finite State Machines
Lecture 23
(Wed 03/03)
Nondeterministic Finite Automata
Section 9
(Thu 03/04)
CFGs, Relations, NFAs, DFAs
Lecture 24
(Fri 03/05)
Regular Languages
Week 10
Lecture 25
(Mon 03/08)
Irregularity
Lecture 26
(Wed 03/10)
Uncountability
Section 10
(Thu 03/11)
Irregularity and Final Review
Lecture 27
(Sat 03/13)
The Halting Problem