Teachings‎ > ‎Undergraduate Courses‎ > ‎

CS133 (WFU and WFW) S1 AY2017--2018

Announcements

The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity. — E. W. Dijkstra
  • 10 Ago 2017: Links to syllabus, academic calendar are now available. First of several slides and required readings (or RR) are now available also.
  • 01 Sep 2017: New DATE for EXAM1 is now 06 September, instead of 01 September.
  • 14 Sep 2017: ALL students please check your bluebook marks versus my record HERE for exam1. You have till next week for corrections. Answer keys are posted at room 317.
  • 02 Oct 2017: Required reading 2 and 3, i.e. RR2 and RR3, now available.
  • 12 Oct 2017: All lecture slides for exam 3 (till day 23) are now uploaded. Reviewer for exam 3 is also uploaded. Be sure to answer exercises in the Sipser book till Chapter 5 for exam 3 also.
    • Day 23 slides update: corrected and improved proof for L_{ne} not in REC.
  • 17 Oct 2017: No class on 18 October, Wednesday, to make room for more preparation for exam 3. Consultations or corrections of exam 2 will be entertained during class hours at room 317 or 319.
  • 26 Oct: Results of exam 3 for both sections can be obtained from me tomorrow, 27 October (Friday) during class hours, i.e. 10:00h--11:30h and 13:00h--14:30h, at either room 317 or 319.
    • As I mentioned in our lecture last 25 October (Wed) I will be away for ~1 month so keep checking my emails and this class page for updates. Sir Kelvin Buño will finish the last and few remaining lectures for exam 4. Corresponding concerns (e.g. consultations, exam clarifications) are also by sir Kelvin through email (kelvin_buo at yahoo dot com) or his consultation hours.
    • Those with valid excuse for missing exam 3, stay tuned for the date of your special exam.
    • We have no classes on 27 October and 01 November.
  • 27 Oct: Marks for both classes in my record are found HERE.
    • Slides for day 24 and required reading 5 (DNA computing for NP complete problems) now available.
  • 01 Nov: No class on 03 November.
  • 02 Nov: For those who notified me their valid excuse, Schedule of special exam 3 is Monday, 06 November, from 1:30PM to 3PM. Please see sir Kelvin Buño for the exam, either at room 317 or 319.
  • 17 Nov: Exam 4 is tentatively scheduled on 29 November.
  • 22 Nov: Reviewer for exam 4 is now available.
  • 07 Dic: You can receive your exam 4 personally from sir Kelvin today or next week (Monday or Tuesday). Please be guided accordingly. Removal exam date and those who will take it will be announced soon.
    • UPDATE: Pre-final grades for WFU and WFW can be downloaded HERE. If your verdict is ``removal'' you need to take the removal exam on 15 December, 2017 (Friday) tentatively at 10AM to 12PM for both WFU and WFW. Room is TBA.

 Weektopics Slides / Materials
1Introduction,
regular languages and finite automata, regular operations.
Day 1
RR1
Day 2
Day 3
Nondeterministic finite automata,
equivalence of DFA and NFA,
Minimization of states. 
Day 4
Day 5
Regular expressions,
equivalence of regular expressions to finite automata.
 
Nonregular languages, Pumping lemma,
Review for exam 1,
EXAM1 (06 September 2017)
Day 6 
exam1 reviewer
 5 CFLs, CFGs,
CFG in CNF, closure properties
Day 9
Day 10
Day 11 
PDAs,
CFGs and PDAs
 Day 12
Day 13
problem set for exam2
DPDA,
NonCF languages,
Review for exam2 
Day 14 
EXAM2 (27 September 2017)  
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 (20 October) 
11Reducibility,
Time complexity and complexity classes
Day 24
RR5
Day 25
Day 26
reviewer
 EXAM4 (29 November)  
 REMOVAL EXAM (15 December)  

  • Syllabus is available HERE.
  • Academic calendar for AY2017--2018 is HERE.