Teachings‎ > ‎Undergraduate Courses‎ > ‎

CS133 sem 2, AY 2016--2017

Semester 2, AY 2016 to 2017
 by F. Cabarle, K. Buño,  and H. Adorna

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, THU-1, THZ, THZ-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
  • Syllabus for all four sections is HERE.
  • 06 Feb: The date for EXAM 1 is set on 14 Feb 2017.
    • Please also read the article ``reading1'' for exam 1.
  • 09 Feb: I apologize, but I cannot come to the department today for CS133 consultations. For concerns regarding some points of the class discussions, you can send an email (kelvin_buo@yahoo.com). - K. Buño
    • We have decided that the instructors will be providing all the bluebooks for each student for the examinations. For those who have submitted their bluebooks beforehand, we will give you back a new bluebook for each bluebook you have submitted.
  • 01 May: For those who have a valid excuse for missing exam 3, the schedule for the makeup exam 3 on 04 MAY, THURSDAY, is as follows (BRING excuse letter from UP Health Service, otherwise no makeup exam 3):
    • THU-1: 10AM to 11:15AM, room 319.
    • THZ and THZ-1: 5:30PM to 6:45PM, room 319.
  • 02 May: UPDATED date of exam 4 for THU-1, THZ, and THZ-1 is 09 May, 2017 (Tuesday).
  • 16 May: THZ-1 Class Standings is now available. Two students from THZ-1 are required to take the finals. Those who took a leave of absence or those who dropped the course will get a grade of DRP. The schedule of the final exam will be announced later.
  • 17 May
    • The final exam is scheduled on 24 MAY 2017, WEDNESDAY, 1300H-1600H, ERDT Room. 
    • Pre-final standing: THU-1 and THZ. For those who passed already, not need to take the removal exam. You can email or see personally to see your grade.
  • 24 May:
    • THZ-1 Class Standing updated to include grades of removal exam takers.
    • Updated grades for THU-1 and THZ, to include the results of the removal exam.
    • ANY changes, email or see us personally until FRIDAY this week, 26 May 2017. After Friday this week, your grades will be finalized and submitted to CRS.
Date(s)  Lesson(s)Resource(s) 
17 JanIntroduction Day 01
24 Jan
26 Jan
31 Jan
Regular languages and finite automataDay 02
Day 03
Day 04
2 Feb
 Regular Expressions
Day 05
7 Feb
Non-Regular Languages and Pumping Lemma
 Day 06
 9 Feb
Review for EXAM 1
Problem Set, reading1
14 Feb
16 Feb
21 Feb
23 Feb
 Context-Free Languages and Grammars
Day 09
Day 10
Day 11
 28 Feb
2 Mar
 Pushdown Automata
Day 12
Day 13
 7 Mar
 Pumping Lemma for Context-Free Languages
Day 14
9 Mar
Review for EXAM 2
 Problem Set
 14 Mar
  Turing machines, Turing recognizable and decidable languages
Day 17Day 18

 Turing machine variants, Turing-Church thesis, further topics on computability,
 Day 19reading2
problem setreading3,
Day 20 (reading 4, review of Chomsky hierarchy),
Day 21Day 22
18 AprilEXAM 3
Time complexity classes,
More on time complexity, intractability,
Further topics on computability and complexity theory
Day 23 and Day 24,
Day 25,
problem set 1 of 2,
Day 26problem set 2 of 2
 09 MayEXAM 4  

Relevant holiday(s) as per UPD AY2016 to 2017 calendar:
  • 09 April, Sunday.
  • 13 to 14 April, Thursday to Friday.
  • 01 May, Monday.