Teachings‎ > ‎Undergraduate Courses‎ > ‎

CS 133 Sem 1, AY 2016 to 2017

Semester 1, AY 2016 to 2017
 by F. Cabarle 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 THX, THZ, THZ-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
  • 10 Ago: Course syllabus can be downloaded HERE.
  • 11 Ago: Supplementary (required) reading now uploaded, see Resource(s) table.
  • 31 Ago: Please check the updated table of dates.
  • 05 Sep: New schedule for exam 1 of THZ and THZ-1 is now on 13 SEPTEMBER 2016.
  • 08 Sep: Exam results for class THX can be found HERE. Please check that your scores in our records are exactly those on your exams.
  • 20 Sep: Exam results for class THZ-1 can be found HERE.
  • 27 Oct: No class today for CS133 THX, THZ, and THZ-1. Happy (relatively long) weekend!
  • 08 Nov: The link to the Springer book chapter for ``Classic Nintendo Games Are (Computationally) Hard'' is HERE (you can download the chapter for free within DilNet). A pre-print version of the same chapter is available for free HERE.
  • 10 Nov: No class today for THX, THZ, THZ-1. Please answer the problem set 1 (of 2) HERE. Happy weekend, and see you next week!
  • 15 Nov: Additional (animated) slides on proof of NP-completeness of SAT is HERE.
  • 29 Nov: THZ and THZ-1, you can obtain your exam 4 bluebooks today (Tuesday) at room 317 or 319, from 4PM to 6PM.
  • 01 Dec: Final (removal) exam will be on 06 December (Tuesday), from 5:30PM to 7PM at class room 1.
  • 07 Dec: If you have not done so, please check the score sheet for THX and THZ-1, HERE and HERE, respectively. Please email me (Francis) if you have doubts or concerns regarding the scores of your four exams. Your grades will be final by 12 December (Monday of next week).
Date(s)  Lesson(s)Resource(s) 
09 AgoIntroduction Day 01
11 Ago
16 Ago
18 Ago
 Finite automata and regular languagesDay 02, reading1
Day 03
Day 04
23 AgoRegular expressionsDay 05
25 Ago
30 Ago
Pumping lemma for regular languages
Review
Day 06, problem set
01 SepEXAM 1 (canceled for THZ, THZ-1) 
06 Sep
08 Sep

13 Sep
 Context-free grammars y languages


EXAM 1 for THZ, THZ-1 (new schedule)
Pushdown automata
Day 09
Day 10 y Day 11


Day 12
15 Sep
20 Sep
Pushdown automataDay 13, problem set
22 Sep
27 Sep
Pumping lemma for context-free languages
Review
Day 14
29 SepEXAM 2
04 Oct
06 Oct
Turing machines, Turing recognizable and decidable languages  Day 17, Day 18
11 Oct

13 Oct
Turing machine variants, Turing-Church thesis, further topics on computability,
(un)decidability
Day 19reading2
problem setreading3,
Day 20 (reading 4, review of Chomsky hierarchy),
Day 21, Day 22,
Day 23
18 OctReview 
25 Oct
03 Nov
Exam 3
Time complexity classes

Day 24
08 Nov
15 Nov
17 Nov
More on time complexity, intractability
Further topics
on computability and complexity theory
Day 25,
reading5,
problem set 1 of 2,
Day 26, problem set 2 of 2
22 Nov
24 NovEXAM 4
 
06 DecFINAL EXAM (5:30PM to 7PM, class room 1) 

Relevant holiday(s) as per UPD AY2016 to 2017 calendar:
  • 01 Nov (Tue): All saints day