Semester 1, 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 WFW-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
- 14 ago: syllabus now uploaded! Also, for each exam there is at least 1 required reading or RR. Please make sure you read these RR since they are included in the exams.
| | Week | topics | Materials | | 1 | Introduction,
regular languages and finite automata, regular operations. | Day 1
RR1
Day 2
Day 3 | | 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 () | 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
problem set for exam2 | | 7 | DPDA,
NonCF languages,
Review for exam2 | Day 14 | | 8 | EXAM2 () | | | 9 | Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM | RR3, RR4
Day 17
Day 18
Day 19 | | 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 | | | EXAM3 () | | | | REMOVAL EXAM () | |
- Syllabus HERE.
- View the UP Diliman academic calendar here: https://upd.edu.ph/
|
|
