CS133 sem 2, AY 2016--2017

Semester 2, AY 2016 to 2017

 by F. Cabarle, K. Buño,  and H. Adorna

The introduction of suitable abstractions is our only mental aid to reduce the appeal to enumeration, to organize and master complexity. — E. W. Dijkstra

     

Date(s) 

17 Jan

24 Jan

26 Jan

31 Jan

2 Feb

7 Feb

 9 Feb

14 Feb

16 Feb

21 Feb

23 Feb

 28 Feb

2 Mar

 7 Mar

9 Mar

 14 Mar

 

 

18 April

 

 09 May

YY May 

 Lesson(s)

Introduction 

Regular languages and finite automata

 Regular Expressions

Non-Regular Languages and Pumping Lemma

Review for EXAM 1

EXAM 1

 Context-Free Languages and Grammars

 Pushdown Automata

 Pumping Lemma for Context-Free Languages

Review for EXAM 2

EXAM 2

 Turing machines, Turing recognizable and decidable languages

Turing machine variants, Turing-Church thesis, further topics on computability,

(un)decidability 

EXAM 3

 Reduction,

Time complexity classes,

More on time complexity, intractability,

Further topics on computability and complexity theory

EXAM 4 

FINAL (REMOVAL) EXAM 

Relevant holiday(s) as per UPD AY2016 to 2017 calendar: