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)
17 Jan
24 Jan
26 Jan
31 Jan
2 Feb
7 Feb
9 Feb
14 Feb
16 Feb
21 Feb
23 Feb
28 Feb
2 Mar
7 Mar
9 Mar
14 Mar
18 April
09 May
YY May
Lesson(s)
Introduction
Regular languages and finite automata
Regular Expressions
Non-Regular Languages and Pumping Lemma
Review for EXAM 1
EXAM 1
Context-Free Languages and Grammars
Pushdown Automata
Pumping Lemma for Context-Free Languages
Review for EXAM 2
EXAM 2
Turing machines, Turing recognizable and decidable languages
Turing machine variants, Turing-Church thesis, further topics on computability,
(un)decidability
EXAM 3
Reduction,
Time complexity classes,
More on time complexity, intractability,
Further topics on computability and complexity theory
EXAM 4
FINAL (REMOVAL) EXAM
Relevant holiday(s) as per UPD AY2016 to 2017 calendar:
09 April, Sunday.
13 to 14 April, Thursday to Friday.
01 May, Monday.