|
COL352: Introduction to Automata and Theory of Computation
|
Announcements |
|
Instructor |
Naveen Garg, 515 Bharti |
Text |
Introduction to Automata Theory. Languages and Computation;
Hopcroft,
Motwani and Ullmann; Pearson Education |
Reference
Material |
- Elements of the Theory of Computation; Lewis and
Papadimitriou;
Pearson
Education
- Automata and Computability; Kozen
|
Course
outline (tentative) |
Topic |
Slides
|
Tentative Dates
|
Introduction
|
intro
|
4
|
Regular expressions
|
1, 2, 3
|
8
|
Finite Automata - deterministic and non-deterministic
|
1, 2, 3 |
11, 13
|
Regular languages, properties, pumping lemma
|
|
15, 18
|
Context-free languages
|
1, 2, 3 |
|
Pushdown Automata
|
1, 2 |
|
Properties of CFLs
|
1, 2 |
|
Turing Machines
|
1, 2 |
|
Decidability and Undecidability
|
1, 2 |
|
P, NP, Polytime reductions
|
1, 2, 3 |
|
P-Space completeness
|
1 |
|
|
Tutorial Sheets
|
Date given
|
Tutorial Sheet
|
Solutions
|
Jan 12
|
tut1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Evaluation |
Minor1 (20); Minor2 (25);
Major (40); 4 surprise lecture quizzes, best 3 to be counted, weightage of 5 marks each
|
Attendance/missed
tests Policy
|
If you miss a minor due to
illness (medical certificate needed) then I
will scale the marks you receive in the other minors and major to
award you marks in the missed minor. There is no reminor. If you miss a lecture quiz there is no possibility of compensating it.
|