cs133

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.
  • 23 ago: As announced in class earlier this week, EXAM 1 is on 29 August 2018. Please be sure to work on the exam reviewer and read the RR.
  • 27 ago: Quiz 1 and 2 results can be obtained from me on Tuesday, 28 August 2018, at room 317 or 319 from 16:30h to 17:00h, otherwise I will release them after exam 1 on Wednesday.
  • 18 sep: New resources have been added: Links to creating and simulating DFA, CFG, PDA using the JFLAP simulator. 
  • 23 oct: More resources added, e.g. Links to JFLAP simulator for TMs, short animated video on complexity of counting and all Eulerian paths in a graph. Enjoy!
  • 12 nov: As announced by sir Kelvin last week, our exam 3 coincides with their exam 3, i.e. Exam 3 is on 21 November, 1PM to 2:30PM. FYI and thanks.
    • Quiz 6 this week will also be by sir Kelvin. Please be sure to take this quiz.
  • 21 nov: Part 2 of Exam 3, only for WFW-1 students is HERE. Please read the instructions carefully.
    • UPDATE: Sorry for the confusion. Deadline is before 24 November 2018, i.e. on or before 11:59PM, GMT+8, of 23 November 2018.
  • 27 nov: You can obtain your exam 3 part 1 and quiz 6 from sir Kelvin on Thursday this week, 29 November, between 12pm and 3pm at room 319 or 317.
    • Update: sir Kelvin told me that you can obtain your exam 3 part 1 now in a paper box just outside room 319.
  • 02.12: By now all of you should have received a direct email from me re: your pre-final grade. For those who need to take the removal exam, the date of the removal exam is 6 December 2018, Thursday at 1PM (Room is TBA), with sir Kelvin. Please email us for any doubts about your CS133 marks.
  • 04.12: For those who need to take the removal exam, Removal exam for CS133 WFW-1, together with other classes of sir Kelvin, is on 6 December 2018 (Thursday), 1PM at CLR4 (Classroom 4).

``The best theory is inspired by practice. The best practice is inspired by theory.''
-- Donald E. Knuth
 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 (29 August 2018)
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 (28 September 2018)  
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, Part 1 (21 November 2018)
EXAM3, Part 2
 
 
 REMOVAL EXAM ()  

  • Syllabus HERE.
  • View the UP Diliman academic calendar here: https://upd.edu.ph/