cs133

Semester 2, AY 2017 to 2018
 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 THU-1 and THW-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
  • 22 Ene: schedule for the sem has been updated, with Exam months included, but no days yet. Required reading 1 or RR1 for exam 1 is available, and will be included in the exam! 
 Weektopics Slides / Materials
1Introduction,
regular languages and finite automata, regular operations.
Day 1
RR1
Day 2
Day 3
Nondeterministic finite automata,
equivalence of DFA and NFA,
Minimization of states. 
Day 4
Day 5
Regular expressions,
equivalence of regular expressions to finite automata.
 
Nonregular languages, Pumping lemma,
Review for exam 1,
EXAM1 (February 2018)
Day 6 
exam1 reviewer
 5 CFLs, CFGs,
CFG in CNF, closure properties
Day 9
Day 10
Day 11 
PDAs,
CFGs and PDAs
 Day 12
Day 13
problem set for exam2
DPDA,
NonCF languages,
Review for exam2 
Day 14 
EXAM2 (March 2018)  
Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM
RR2RR3
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 (RR4)
Day 21
Day 22
Day 23
reviewer
  EXAM3 (April 2018) 
11Reducibility,
Time complexity and complexity classes
Day 24
RR5
Day 25
Day 26
reviewer
 EXAM4 (May 2018)  
 REMOVAL EXAM (May 2018)  

  • Syllabus is available HERE.
  • Academic calendar for AY2017--2018 is HERE.