Semester 2, AY 2017 to 2018 by Francis George C. Cabarle
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-1 and THW-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
- 22 Ene: schedule for the sem has been updated, with Exam months included, but no days yet. Required reading 1 or RR1 for exam 1 is available, and will be included in the exam!
- 27 Feb: Results for exam 1 of both classes have been released in-class. Answer keys are posted at room 319. NOTE the updated tentative dates for exam 2 and 3.
- 26 Mar:
- For THW-1: Since we were not able to hold classes last week due to transport strikes and ACLE, I am adding to your reading list this week day 18. Day 18 simply continues the introduction of Turing machines form day 17, with a few more examples taken from the Sipser book and other sources of folkore.
- Both THU-1 and THW-1: Use this week to read THREE (3) required readings for exam 3:
- day 20, a review of Chomsky hierarch from exam 1 to exam 3, with a few new minor details, e.g. context-sensitive grammars.
- RR2 and RR3, which are nice and short essays about the contributions of Alan Turing.
- All three required readings will be included in exam 3. Any doubts, please consult me.
- 03 Abr: Results of exam 3 for both classes have been released. Please check room 319 for the answer keys.
- 09 Abr: No class on 10 April, 2018, Tuesday. Please use this extra time to read day20 (RR4), answer the problem set, RR2, and RR3. Last lecture for exam 3 is Thursday this week, and exam 3 is still on 17 April 2018.
- 18 Abr: Date for exam 4 is set to 10 May 2018.
| Week | topics | Slides / Materials | 1 | Introduction, regular languages and finite automata, regular operations. | Day 1 RR1 Day 2 Day 3 | 2 | Nondeterministic finite automata, equivalence of DFA and NFA, Minimization of states. | Day 4 Day 5 | 3 | Regular expressions, equivalence of regular expressions to finite automata. | | 4 | Nonregular languages, Pumping lemma, Review for exam 1, EXAM1 (February 2018) | Day 6 exam1 reviewer | 5 | CFLs, CFGs, CFG in CNF, closure properties | Day 9 Day 10 Day 11 | 6 | PDAs, CFGs and PDAs
| Day 12 Day 13 problem set for exam2 | 7 | DPDA, NonCF languages, Review for exam2 | Day 14 | 8 | EXAM2 (13 March 2018) | | 9 | Turing machines, transducers, Variants (e.g. multitape, nondeterministic), Universal TM | RR2, RR3 Day 17 Day 18 Day 19 | 10 | More on recursive (decidable) and recursively enumerable languages, Noncomputable languages, Chomsky hierarchy so far Review for exam3 | Day 20 (RR4) Day 21 Day 22
Day 23 reviewer | | EXAM3 (17 April 2018) | | 11 | Reducibility, Time complexity and complexity classes | Day 23 Day 24 RR5 Day 25 Day 26 reviewer | | EXAM4 (10 May 2018) | | | REMOVAL EXAM (May 2018) | |
- Syllabus is available HERE.
- Academic calendar for AY2017--2018 is HERE.
|