Lecture #1
Wed 17/01

Introduction to the course • Admin and logistics • Brief history of computing


PS0 released Register on Ed Discussions

Lecture #2
Fri 19/01

Languages vs problems • Alphabets, strings and languages
[notes]



Lecture #3
Tue 23/01

Languages and Problems • Uncountability of the set of all languages • Machine models
[notes]



Lecture #4
Wed 24/01

Programs with readonce inputs and bounded memory  states and transitions • DFAs  formal definition • Examples
[notes]

 Section 2.1, 2.2.1, 2.2.2  [HMU]


Lecture #5
Mon 29/01

DFA  formal definition, notion of acceptance, regular languages, examples • Formal proof correctness of construction  examples
[notes]



Lecture #6
Tue 30/01

DFA  proving correctness • Operations on languages  union, intersection, concatenation, Kleene star, examples • Closure properties of regular languages
[notes]


PS1 released

Lecture #7
Wed 31/01

Closure properties of regular languages  union, intersection, complement, examples • Concatenation of regular languages  the need to guess
[notes]



Tutorial #1
Fri 02/02

Based on Problem sets 0 and 1



Lecture #8
Mon 05/02

Nondeterminism  examples and definitions • Equivalent models  multiple start states, \( \varepsilon \)transitions
[notes]

 Sections 2.3.1 to 2.3.4  [HMU]


Lecture #9
Tue 06/02

Equivalent definitions  multiple start states, \( \varepsilon \)transitions, examples • Concatenation and Kleene star using NFAs • From NFAs to DFAs
[notes]



Lecture #10
Wed 07/02

Equivalence of NFAs and DFAs  construction and examples • More closure properties using NFAs
[notes]



Test #1
Fri 09/02

Based on Lectures 1  7 (Problem sets 0 and 1)



Lecture #11
Mon 12/02

Nonregular languages  examples and proof ideas • Formalizing the idea  statement of the pumping lemma
[notes]


PS2 released

Lecture #12
Tue 13/02

Pumping lemma  statement and proof • Contrapositive form  examples
[notes]



Lecture #13
Wed 14/02

Pumping lemma  more examples and uses
[notes]



Tutorial #2
Fri 16/02

Based on Problem set 2



Lecture #14
Mon 19/02

Distinguishable and indistinguishable strings • Using distinguishable strings to prove nonregularity • Indistinguihability as an equivalence relation
[notes]



Quiz #1
Tue 20/02

Based on Lectures 1  13 (Problem sets 0, 1, and 2)



Lecture #15
Wed 21/02

MyhillNerode relations • Indistinguishability relation as a MyhillNerode relation • From DFAs to MyhillNerode relations
[notes]



Lecture #16
Fri 23/02

From MyhillNerode relations to DFAs  construction, examples • Coarsest MyhillNerode relation
[notes]



Lecture #17
Tue 27/02

Coarsest MyhillNerode relation • Uniqueness of minimal DFA • Quotient construction and the minimization algorithm
[notes]


PS3 released

Lecture #18
Wed 28/02

Quotient construction and minimization algorithm • Regular expressions
[notes]



Tutorial #3
Fri 01/03

Based on Problem set 3



Lecture #19
Mon 04/03

Regular expressions  pattern matching, examples • From regular expressions to DFAs  construction, examples, complexity
[notes]



Lecture #20
Tue 05/03

From DFA to regex  state elimination, examples • Decision problems on regular languages and their complexity
[notes]

 Sections 3.2.2, 4.3  [HMU]


Test #2
Wed 06/03

Based on Lectures 14  18 (Problem set 3)



Lecture #21
Mon 11/03

ContextFree Languages(CFL)  motivation, definition • ContextFree Grammars (CFG)  examples, derivations
[notes]


PS4 released

Lecture #22
Tue 12/03

ContextFree Grammars (CFG)  more examples and constructions, the Dyck language
[notes]



Lecture #23
Wed 13/03

Dyck language (contd) • Regular languages and linear grammars • Parse trees
[notes]



Tutorial #4
Fri 15/03

Based on Problem set 4



Lecture #24
Mon 18/03

Ambiguity in grammars  leftmost derivations and parse trees • Examples  arithmetic expressions, dangling else • Closure properties of CFLs
[notes]



Quiz #2
Tue 19/03

Based on Lectures 14  20 (Problem sets 3 and 4)



Lecture #25
Wed 20/03

Chomsky Normal Form  removing unit productions and \( \varepsilon \)productions
[notes]



Lecture #26
Fri 22/03

Chomsky Normal Form • Pumping lemma for CFLs  statement and examples
[notes]


PS5 released

Lecture #27
Tue 26/03

Pumping lemma for CFLs  examples • Closure properties of CFL
[notes]



Tutorial #5
Wed 27/03

Based on Problem set 5



Lecture #28
Mon 01/04

CockeKasamiYounger (CKY) algorithm for parsing CFGs
[notes]



Lecture #29
Tue 02/04

Pushdown Automata (PDA)  definitions, acceptance conditions, examples
[notes]



Lecture #30
Wed 03/04

Equivalence of PDAs and CFGs
[notes]


PS6 released

Tutorial #6
Fri 05/04

Based on Problem set 6



Lecture #31
Mon 08/04

Equivalence of PDAs and CFGs (contd.) • Effective computability
[notes]



Lecture #32
Wed 10/04

Turing machines  motivation, definition, examples, configurations and acceptance condition
[notes]



Lecture #33
Fri 12/04

Recursive and recursively enumerable languages • Multitape TMs • Universal TM
[notes]


We covered parts of these lectures. Check the notes for the exact portions

Lecture #34
Mon 15/04

Recursive and recursively enumerable languages • Membership problem (MP) and Halting problem (HP) • Enumeration machines
[notes]



Test #3
Tue 16/04

Based on Lectures 21  30 (Problem sets 5 and 6)



Lecture #35
Wed 17/04

Diagonalization  undecidability of the Halting Problem
[notes]



Lecture #36
Thu 18/04

Reducibility between problems  Halting Problem, Membership Problem and other examples
[notes]



Lecture #37
Mon 22/04

Manyone reductions  examples
[notes]



Lecture #38
Tue 23/04

Manyone reductions  examples • Statement of Rice's theorem
[notes]


PS7 released

Lecture #39
Wed 24/04

Rice's theorem  examples, proof
[notes]



Lecture #40
Thu 25/04

Problems on CFLs • Valid computation histories  proof ideas
[notes]



Tutorial #7
Fri 26/04

Based on Problem set 7



Lecture #41
Mon 29/04

Notion of timecomplexity • Efficient computation and complexity class P



Lecture #42
Tue 30/04

P vs NP  efficient verifiability and search • Reductions, NPcompleteness • CookLevin theorem (statement) • Wrapup of the course



Test #4
Wed 01/05

Based on Lectures 31  40 (Problem set 7)



Tutorial #8
Fri 03/05

Discussion of Class test 4


