CS 204 Theory of Computation [1st Semester AY 08-09]

Theory of Computation
Thursdays, 18.00 to 21.00, CLR 4 UPAE Centennial Hall

Instructor: Henry N. Adorna
email: ha@dcs.upd.edu.ph

Office: ACLab
           Rm 315 UPAE Centennial Hall
           Department of Computer Science,
           Velasquez St. UPDiliman, 1101 Q.C.

Consultation: By appointment

Course Requirements:

1. There will be two exams in a semester.
2. There will be an oral report presentation towards the end of the semester.

Grades:

Grades will be based on the result of the examinations (60 %) and the oral presentation (40%).


References:

1.  Kozen, Dexter.  Theory of Computation, Springer, 2006
2.  Kozen, Dexter.  Automata and Computability, Springer, 1997
3.  Hopcroft, J. Motwani, R., Ullman, J.  Introduction to Automata Theory,Languages and Computation, Addison-Wesley, 2001
4.  Homer, S., Selman A..  Computability and Complexity Theory, Springer, 2001
5.  Hromkovic, Juraj. Theoretical Computer Science, Springer, 2004
6.  Sipser, Michael.  Introduction to the Theory of Computation 2ed, Thomson Course Technology, 2006

 Schedule of Classes

 Day  Date   Topics Notes
 1 12.06.08 Intro to TCS
 lecture 1
    Lectures 2 to 4 is primarily based on the lecture notes G.Grahne using reference 3.
 219.06.08 Regular Languages, FAs and Regular Expressions
 lecture 2
 3 26.06.08 Context-Free Grammar and  Languages
 lecture 3
 4 03.07.08 PDA and CFG
 lecture 4
    Lecture  5 uses notes obtain from Pierre Flener notes using reference 3.
 5 10.07.08  Non-CFL and Turing Machine (1)
 lecture 5
 6 17.07.08 Non-CFL and Turing Machine (2) lecture 6
 7 24.07.08 Non-CFL and Turing Machine (3)
 lecture 7
 8 31.07.08 First Long Exam :
Lecture 1 to Lecture 7
 
 9 07.08.08 no classes
 
       10                     14.08.08 Discussion about the examination
 
 11 21.08.08 no Classes
 
    Lectures below are obtained from reference number 4
lectures 8-10
 12 28.08.08 Intro to Computability
 lecture 8
 13 04.09.08 Undecidability(1) lecture 9
 14 11.09.08Undecidability (2)
 lecture 10
 1518.09.08
Basic Results of Complexity Theory
readings/
no lecture
 16 25.09.08 Nondeterminism and NP-Completeness
 lecture 11
(www.cs.binghamton.edu/
~dima/cs333)
 17 02.10.08 Oral Report
 
   Ontology View on Automata Theory
D. Wuysang
M. Barsobia
A. Razon
   Team Automata for Security
S. Roxas
J. Roque
   Some Application of FSA Theory to NLP
E. Cabalfin
J. Aquinde
 18 09.10.08 Automata Theory for XML Researchers
C. Alegre
A. Jayme
P. Uy
  Using FSA for Sequence Mining
N. Ramos
J. Lib-atin
O. Berris
   Automata Theory approach for solving Frequent Pattern Discovery Problem
D. Ong
M. Agana
J. Mabalot
  An FSA based Data Mining Algorithm
J. Vargas
D. Diamante
E.
    

Ċ
henry adorna,
Jul 6, 2008, 3:06 AM
Ċ
Henry Adorna,
Jul 16, 2008, 10:58 PM
Ċ
Henry Adorna,
Sep 14, 2008, 4:16 PM
ć
np.ppt
(215k)
Henry Adorna,
Sep 25, 2008, 5:59 PM
Ċ
henry adorna,
Jun 20, 2008, 4:24 PM