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.
|
