Members‎ > ‎Kelvin C. Buño‎ > ‎

CS 133 - Automata Theory and Computability (2nd Semester, AY2017-2018)

Announcements

  • Syllabus for this 2nd Semester AY 2017-2018.
  • [31 Jan 2018] [THU] No class meeting tomorrow, 1 Feb 2018.
  • [14 Mar 2018] [THU] No class meeting tomorrow, 15 Mar 2018.
  • [15 May 2018] [THU] Here is a summary of your exams: CS133THU. Some notes regarding the summary table:
    • Under the 4Pass? column: The value is TRUE if your average is greater than or equal to 60%. FALSE otherwise.
    • Under TakeFE? column: The value is TRUE if you have taken all exams (there will be at least 0.1 pt if you had) AND there are at least two exams greater than or equal to 50% AND the value under 4Pass? is FALSE. Otherwise FALSE.
    • Those who have FALSE under TakeFE? will have their final grades indicated under the tempCRS column. You have until next week (21 May 2018) to check, and if any, submit a complaint for further corrections.
    • For those who must take the Final Exam/Removals, schedule of the exam will be announced later this week.
  • [20 May 2018] [THU] For those who will take the final/removal exam, the set date is on the 24th of May 2018, Thursday, 1300H - 1500H. Please notify me of any conflict.
  • Results for the Finals/Removals:
    • xxxx-xx359 - 27/50 - FAILED
    • xxxx-xx551 - 36/50 - PASSED
    • xxxx-xx265 - 31/50 - PASSED
    • Those that passed the finals/removals, you will be given a grade of 3.00.

Coverage
Topics
Slides / Materials
1st Exam
Introduction
Deterministic Finite Automata
DFA Minimization
Nondeterministic Finite Automata
Regular Expressions
Nonregular Languages and Pumping Lemma
Day 01
Day 02
Day 03
Day 04
Day 05
Day 06
 1st Exam: 13 Feb 2018
Exercise
 2nd Exam
Introduction to Context-Free Grammars
Designing CFG. Ambiguous CFG.
Chomsky Normal Form
Pushdown Automata
Equivalence of PDA and CFG
Non-Context Free Languages
Day 09
Day 10
Day 11
Day 12
Day 13
Day 14
  2nd Exam: 13 Mar 2018
Exercise
 3rd Exam
Introduction to Turing Machines
Transducers
Variants of Turing Machines
Chomsky Hierarchy
 Decidable Problems
Undecidable Problems
Introduction to Reductions
Day 17
Day 18
Day 19
Day 20 (RR)
Day 21
Day 22
Day 23
  3rd Exam:
 reviewer
4th Exam
Introduction to Time Complexity
Class P and NP. Polynomial Time Reduction.
NP-Completeness
Day 24
Day 25
Day 26
 4th Exam: 
 
 Finals/Removals: 24 May 2018