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.