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 Ago||Introduction ||Day 01|
| Finite automata and regular languages||Day 02, reading1|
|23 Ago||Regular expressions||Day 05|
|Pumping lemma for regular languages|
|Day 06, problem set|
|01 Sep||EXAM 1 (canceled for THZ, THZ-1)|| |
| Context-free grammars y languages|
EXAM 1 for THZ, THZ-1 (new schedule)
Day 10 y Day 11
|Pushdown automata||Day 13, problem set|
|Pumping lemma for context-free languages|
|29 Sep||EXAM 2|
|Turing machines, Turing recognizable and decidable languages ||Day 17, Day 18|
|Turing machine variants, Turing-Church thesis, further topics on computability,|
|Day 19, reading2|
problem set, reading3,
Day 20 (reading 4, review of Chomsky hierarchy),
Day 21, Day 22,
|18 Oct||Review|| |
Time complexity classes
|More on time complexity, intractability|
on computability and complexity theory
problem set 1 of 2,
Day 26, problem set 2 of 2
|24 Nov||EXAM 4|| |
|06 Dec||FINAL EXAM (5:30PM to 7PM, class room 1)|| |
- 01 Nov (Tue): All saints day