Semester 1, AY 2018--2019. 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 WFW-1! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
- 14 ago: syllabus now uploaded! Also, for each exam there is at least 1 required reading or RR. Please make sure you read these RR since they are included in the exams.
- 23 ago: As announced in class earlier this week, EXAM 1 is on 29 August 2018. Please be sure to work on the exam reviewer and read the RR.
- 27 ago: Quiz 1 and 2 results can be obtained from me on Tuesday, 28 August 2018, at room 317 or 319 from 16:30h to 17:00h, otherwise I will release them after exam 1 on Wednesday.
- 18 sep: New resources have been added: Links to creating and simulating DFA, CFG, PDA using the JFLAP simulator.
- 23 oct: More resources added, e.g. Links to JFLAP simulator for TMs, short animated video on complexity of counting and all Eulerian paths in a graph. Enjoy!
- 12 nov: As announced by sir Kelvin last week, our exam 3 coincides with their exam 3, i.e. Exam 3 is on 21 November, 1PM to 2:30PM. FYI and thanks.
- Quiz 6 this week will also be by sir Kelvin. Please be sure to take this quiz.
- 21 nov: Part 2 of Exam 3, only for WFW-1 students is HERE. Please read the instructions carefully.
- UPDATE: Sorry for the confusion. Deadline is before 24 November 2018, i.e. on or before 11:59PM, GMT+8, of 23 November 2018.
- 27 nov: You can obtain your exam 3 part 1 and quiz 6 from sir Kelvin on Thursday this week, 29 November, between 12pm and 3pm at room 319 or 317.
- Update: sir Kelvin told me that you can obtain your exam 3 part 1 now in a paper box just outside room 319.
- 02.12: By now all of you should have received a direct email from me re: your pre-final grade. For those who need to take the removal exam, the date of the removal exam is 6 December 2018, Thursday at 1PM (Room is TBA), with sir Kelvin. Please email us for any doubts about your CS133 marks.
- 04.12: For those who need to take the removal exam, Removal exam for CS133 WFW-1, together with other classes of sir Kelvin, is on 6 December 2018 (Thursday), 1PM at CLR4 (Classroom 4).
``The best theory is inspired by practice. The best practice is inspired by theory.'' -- Donald E. Knuth | | Week | topics | Resources | | 1 | Introduction,
regular languages and finite automata, regular operations. | Day 1, RR1
Day 2, Day 3
DFA with JFLAP simulator | | 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 (29 August 2018) | Day 6
exam1 reviewer | | 5 | CFLs, CFGs,
CFG in CNF, closure properties | Day 9, Day 10
Day 11 , RR2 | | 6 | PDAs,
CFGs and PDAs
| Day 12, Day 13
CFG and PDA with JFLAP simulator
problem set for exam2 | | 7 | DPDA,
NonCF languages,
Review for exam2 | Day 14 | | 8 | EXAM2 (28 September 2018) | | | 9 | Turing machines, transducers,
Variants (e.g. multitape, nondeterministic),
Universal TM | RR3, RR4, Day 17
Day 18, Day 19
Turing machines in JFLAP simulator | | 10 | More on recursive (decidable) and
recursively enumerable languages,
Noncomputable languages,
Chomsky hierarchy so far
Review for exam3 | Day 20 (RR5)
Day 21, Day 22
Day 23
reviewer | | | | | | 11 | Reducibility,
Time complexity and complexity classes | Day 23 (PCP example)
Day 24, RR6, Day 25
Day 26 (More on Cook-Levin Theorem,
Some computationally hard games, 3SAT to CLIQUE)
reviewer
Video: Complexity of counting all (Eulerian) paths. | | | EXAM3, Part 1 (21 November 2018)
EXAM3, Part 2 | | | | REMOVAL EXAM () | |
- Syllabus HERE.
- View the UP Diliman academic calendar here: https://upd.edu.ph/
|
