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! 
  • 27 Feb: Results for exam 1 of both classes have been released in-class. Answer keys are posted at room 319. NOTE the updated tentative dates for exam 2 and 3.
  • 26 Mar
    • For THW-1: Since we were not able to hold classes last week due to transport strikes and ACLE, I am adding to your reading list this week day 18. Day 18 simply continues the introduction of Turing machines form day 17, with a few more examples taken from the Sipser book and other sources of folkore.
    • Both THU-1 and THW-1: Use this week to read THREE (3) required readings for exam 3: 
      • day 20, a review of Chomsky hierarch from exam 1 to exam 3, with a few new minor details, e.g. context-sensitive grammars.
      • RR2 and RR3, which are nice and short essays about the contributions of Alan Turing.
    • All three required readings will be included in exam 3. Any doubts, please consult me.
  • 03 Abr: Results of exam 2 for both classes have been released. Please check room 319 for the answer keys.
  • 09 Abr: No class on 10 April, 2018, Tuesday. Please use this extra time to read day20 (RR4), answer the problem set, RR2, and RR3. Last lecture for exam 3 is Thursday this week, and exam 3 is still on 17 April 2018.
  • 18 Abr: Date for exam 4 is set to 10 May 2018.
  • 04 May: Results of exam 3 were released yesterday, 03 May. Answer keys at room 319. Please see me in person or email me if you want to check your class standing.
  • 15 May: Exam 4 results, including pre-final marks and standing, can be inquired tomorrow, 16 May (Wednesday), or 17 May (Thursday), from 2pm to 5pm at room 317 or 319.
  • 18 May: Pre-final grades are now available. Consult me in person or send me an email for inquiry. If no further changes, your grades will be final around next week if you will not take the removal exam. I will send individual emails to those who will take the removal exam. Removal exam is tentatively scheduled on 24 May, 2018 (Thursday) from 1PM to 3PM with room TBA.
  • 21 May: Updated details of removal exam: 24 May, 2018, Thursday from 1PM to 3PM at Classroom 1.
  • 24 May: Please email me for the result of the removal exam. At 5PM of 28 May 2018, Monday, your grades will be final and uploaded to CRS. Any modifications must be done before this date.
 Weektopics Materials
regular languages and finite automata, regular operations.
Day 1
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 
CFGs and PDAs
 Day 12
Day 13
problem set for exam2
NonCF languages,
Review for exam2 
Day 14 
EXAM2 (13 March 2018)  
Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM
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
  EXAM3 (17 April 2018) 
Time complexity and complexity classes
Day 23 (PCP example)
Day 24
Day 25
Day 26 (More on Cook-Levin Theorem
Some computationally hard games, 3SAT to CLIQUE)
 EXAM4 (10 May 2018)  
 REMOVAL EXAM (May 2018)  

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