Foundations of Computation (CPSC 229)—Calendar
Spring Semester, 2017
CalendarLast updated: 04/11/2017 

TOPICS  READINGS  NOTES  
Week 0 (Jan. 18  20) 
propositional logic; boolean algebra  C & E 1.1  1.2  
Week 1 (Jan. 23  27) 
formal deduction; predicate logic  C & E 1.5, 1.4 Notes on Logic 

Week 2 (Jan. 30  Feb. 3) 
mathematical proof; set theory  C & E 1.6, 1.7, 2.1  
Week 3 (Feb. 6  10) 
boolean algebra of sets; power sets; crossproduct sets; functions  C & E 2.2, 2.4  
Week 4 (Feb. 13  17) 
functions; finite and infinite cardinality; countability; recursion  C & E 2.6, 1.9  Assignment #1 due on 02/17 
Week 5 (Feb. 20  24) 
inductivelydefined structures; inductive proof technique  C & E 1.10, 1.8  
Week 6 (Feb. 27  Mar. 3) 
relations and partial orders; formal languages; regular expressions  C & E 2,7, 3.1, 3.2  Assignment #2 due on 03/03 
Week 7 (Mar. 6  10) 
regular expressions; finite automata  C & E 3.4, 3.5  Assignment #3 due on 03/10 
March 13  17  Spring Break (no classes)  
Week 8 (Mar. 20  24) 
DFAs; nondeterminism;  C & E 3.5  Midterm Exam on Friday, March 24 
Week 9 (Mar. 27  31) 
nondeterminism; DFA/NFA equivalence;  C & E 3.5  
Week 10 (Apr. 3  7) 
DFA/NFA equivalence; equivalence of DFAs and regular expressions;  C & E 3.6  Assignment #4 due on 04/06 No class on Friday, 04/07 
Week 11 (Apr. 10  14) 
nonregular languages; contextfree languages; grammars; parse trees;  C & E 3.7, 4.1—4.3  
Week 12 (Apr. 17  21) 
ambiguity; nondeterministic pushdown automata; equivalence with CFLs; noncontext free languages  C & E 4.4—4.5  Assignment #5 due on 04/19 
Week 13 (Apr. 24  28) 
Turing machines; universality; decidable and undecidable problems  C & E 5.1—5.3  Assignment #6 due on 04/28 
Week 14 (May 1  2) 
wrap up  C & E  Final class is Monday, 05/01 Assignment #7 due on 05/05 
Finals Week  Exam time is on Tuesday, 05/09, 1:30p  4:30p 