Foundations of Computation (CPSC 229)—Calendar

Spring Semester, 2017

Calendar

Last 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; cross-product 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)
inductively-defined 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)
non-regular languages; context-free languages; grammars; parse trees; C & E 3.7, 4.1—4.3

Week 12
(Apr. 17 - 21)
ambiguity; nondeterministic pushdown automata; equivalence with CFLs; non-context 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