Semester 1, AY 2019--2020. 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 WFY! Files and announcements will be concatenated to this list, from oldest (top) to newest (bottom). Stay tuned!
- 13.08.2019:
First lecture is on 21 August 2019, Wednesday.- Please Prepare for a possible checkup quiz during the first lecture, by (1) reading Chapter 0 of our reference book by Michael Sipser (see syllabus) and (2) reading RR1 (starting at Section 1,1 What is Computer Science? and so on) see Resources column of the schedule table in this page.
- Remember to check the relative schedules per week of the lectures, exam, e.g. EXAM 1 is Within one (1) month of the start of the lectures, i.e. in at most 4 weeks...
- 19.08.2019: It has come to my attention I made a mistake. FIRST LECTURE is on 23 August 2019, Friday due to a holiday on 21 August. The other details from the 13.08.2019 announcements remain the same.
- 10.09.2019:
- As mentioned last week, EXAM1 is this Friday, i.e. 13 September.
- Quiz for 11 September, please get a copy from room 301. Quiz starts at 4pm, and ends at 5pm of the same day (Wednesday). Please submit your quiz on o before 5pm at room 301. Perfect score is 3 points, with optional bonus questions.
``The best theory is inspired by practice. The best practice is inspired by theory.'' -- Donald E. Knuth | SCHEDULE | 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 (13.09.2019) | 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 | | | 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 | | | | REMOVAL EXAM () | |
- Please find the syllabus (same as previous semester) HERE.
- For holidays and other special events, please view the UP Diliman academic calendar here: https://upd.edu.ph/
|
