cs133

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 THY! Some resources are found in this page, but please make sure to join the corresponding UVLe class also, e.g. for announcements, other materials.
  • For each exam there is at least one article known as required reading or RR. Please be sure to read such articles before the exam.


``The best theory is inspired by practice. The best practice is inspired by theory.''
-- Donald E. Knuth
SCHEDULE

 Weektopics Resources
1Introduction,
regular languages and finite automata, regular operations.
Day 1RR1
Day 2Day 3
DFA with JFLAP simulator
Nondeterministic finite automata,
equivalence of DFA and NFA,
Minimization of states. 
Day 4Day 5
Regular expressions,
equivalence of regular expressions to finite automata.
 
Nonregular languages, Pumping lemma,
Review for exam 1,
EXAM1
Day 6 
exam1 reviewer
 5 CFLs, CFGs,
CFG in CNF, closure properties
Day 9Day 10
Day 11 , RR2
PDAs,
CFGs and PDAs
 Day 12Day 13
CFG and PDA with JFLAP simulator
problem set for exam2
DPDA,
NonCF languages,
Review for exam2 
Day 14 
EXAM2 
Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM
RR3RR4Day 17
Day 18Day 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 21Day 22
Day 23
reviewer
   
11Reducibility,
Time complexity and complexity classes
Day 23 (PCP example)
Day 24RR6Day 25
Day 26 (More on Cook-Levin Theorem
Some computationally hard games, 3SAT to CLIQUE)
reviewer
Video: Complexity of counting all (Eulerian) paths.
 EXAM3 
 REMOVAL EXAM 

  • Please find the syllabus (similar to previous semesters) HERE.
  • For holidays and other special events, please view the UP Diliman academic calendar here: https://upd.edu.ph/