COL352: Introduction to Automata and Theory of Computation

Announcements First class would be on Jan 4 at 11am
Instructor Naveen Garg, 515 Bharti
Text Introduction to Automata Theory. Languages and Computation; Hopcroft, Motwani and Ullmann; Pearson Education
Reference Material
  1. Elements of the Theory of Computation; Lewis and Papadimitriou; Pearson Education
  2. Automata and Computability; Kozen
Course outline (tentative)
Topic Slides
Tentative Dates
Introduction
intro
4
Finite Automata - deterministic and non-deterministic
1, 2, 3
5, 9, 11, 16
Regular expression and languages
1, 2, 3 18, 23, 25, 28, 30
Context-free languages
1, 2, 3 6, 8, 9
Pushdown Automata
1, 2 13, 15, 20
Properties of CFLs
1, 2 22, 6.3, 8, 15, 16,
Turing Machines
1, 2 18, 20, 27, 29
Decidability and Undecidability
1, 2 3, 5, 6
P, NP, Polytime reductions
1, 2, 3 10, 17, 19
P-Space complete
1 26, 27
Problem Solving Sessions
Hours: Roughly every third week we will extend the thursday class (12-2pm) and use it for problem solving.

Dates
Tutorial Sheet
Solutions
12 Jan


16 Feb


9 March


30 March


20 April



Evaluation Minors (5X14), Major (26), Attendance (4). The dates for the 3 in-class minors are: Minor 0.5 (19 Jan), Minor 1.5 (23 Feb), Minor 2.5 (12 April)
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.