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 2 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.
- 04 May: Results of exam 3 were released yesterday, 03 May. Answer keys at room 319. Please see me in person or email me if you want to check your class standing.
- 15 May: Exam 4 results, including pre-final marks and standing, can be inquired tomorrow, 16 May (Wednesday), or 17 May (Thursday), from 2pm to 5pm at room 317 or 319.
- 18 May: Pre-final grades are now available. Consult me in person or send me an email for inquiry. If no further changes, your grades will be final around next week if you will not take the removal exam. I will send individual emails to those who will take the removal exam. Removal exam is tentatively scheduled on 24 May, 2018 (Thursday) from 1PM to 3PM with room TBA.
- 21 May: Updated details of removal exam: 24 May, 2018, Thursday from 1PM to 3PM at Classroom 1.
- 24 May: Please email me for the result of the removal exam. At 5PM of 28 May 2018, Monday, your grades will be final and uploaded to CRS. Any modifications must be done before this date.
| | Week | topics | 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 (PCP example)
Day 24
RR5
Day 25
Day 26 (More on Cook-Levin Theorem,
Some computationally hard games, 3SAT to CLIQUE)
reviewer | | | EXAM4 (10 May 2018) | | | | REMOVAL EXAM (May 2018) | |
- Syllabus is available HERE.
- Academic calendar for AY2017--2018 is HERE.
|
