Semester 2, AY 2018--2019. by Francis George C. Cabarle
``The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity.'' — E. W. Dijkstra
- Welcome to the class web page for CS 133 WFY! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
- 15-02-2019: Exam 1 is on 22 Feb 2019.
- 27-02-2019: Please obtain your quiz 2 and exam 1 papers from ma'am Judith Martinez at the DCS admin office.
``The best theory is inspired by practice. The best practice is inspired by theory.'' -- Donald E. Knuth | | Week | topics | Resources | | 1 | Introduction,
regular languages and finite automata, regular operations. | Day 1, RR1
Day 2, Day 3
DFA with JFLAP simulator | | 2 | Nondeterministic finite automata,
equivalence of DFA and NFA,
Minimization of states. | Day 4, Day 5 | | 3 | Regular expressions,
equivalence of regular expressions to finite automata. | | | 4 | Nonregular languages, Pumping lemma,
Review for exam 1,
EXAM1 (22 Feb 2019) | Day 6
exam1 reviewer | | 5 | CFLs, CFGs,
CFG in CNF, closure properties | Day 9, Day 10
Day 11 , RR2 | | 6 | PDAs,
CFGs and PDAs
| Day 12, Day 13
CFG and PDA with JFLAP simulator
problem set for exam2 | | 7 | DPDA,
NonCF languages,
Review for exam2 | Day 14 | | 8 | EXAM2 (TBA) | | | 9 | Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM | RR3, RR4, Day 17
Day 18, Day 19
Turing machines in JFLAP simulator | | 10 | More on recursive (decidable) and
recursively enumerable languages,
Noncomputable languages,
Chomsky hierarchy so far
Review for exam3 | Day 20 (RR5)
Day 21, Day 22
Day 23
reviewer | | | | | | 11 | Reducibility,
Time complexity and complexity classes | Day 23 (PCP example)
Day 24, RR6, Day 25
Day 26 (More on Cook-Levin Theorem,
Some computationally hard games, 3SAT to CLIQUE)
reviewer
Video: Complexity of counting all (Eulerian) paths. | | | EXAM3 (TBA) | | | | REMOVAL EXAM () | |
|
