CSL705: Theory of Computation (3-1-0-4)
II Semester 2011-012
Instructor: S. Arun-Kumar
Last modified: Thu May 10 13:34:41 IST 2012
Roll list
Lectures:
Slot J
Day
Time
Place
Monday
12:00-12:55
IIA 204
Tuesday
12:00-12:55
IIA 204
Wednesday
12:00-12:55
IIA 204
Tutorials:
Friday 12:00-12:55 IIA 305
Attendance Policy:
Proportional Additive [
w
i
= 0.1
]
Evaluation
Audit Pass: minimum
B
grade
Minor I
20%
Mon 06 Feb 2012
14:30-15:30
WS 213
Solutions to Minor I
Minor II
20%
Sat 24 Mar 2012
14:30-15:30
WS 213
Solutions to Minor II
Assignments (Handwritten)
10%
Quizzes
15%
Best
n-1
out of
n
Major
35%
Wed 02 May 2012
18:00-20:00
WS 213
Solutions to Major
Tutorials
Topic (Handwritten Assignments)
Submission deadline
Strings and Numbers
23 Jan 2012
DFAs and Regular Languages
30 Jan 2012
Regular-expressions, Regular grammars and pumping lemma
10 Feb 2012
Context-free Grammars
02 Mar 2012
NPDAs
30 Mar 2012
Turing Machines and Turing Computability
10 Apr 2012
Primitive Recursion and Universality
27 Apr 2012
References
Arun-Kumar S
:
Theory of Computation-II
Draft Lecture notes (Automata and Languages)
Arun-Kumar S
:
Handwritten Notes
Turing Machines - A Standard Model
Turing Machines As Acceptors
Turing Computability in Other Domains
Arithmetization of Turing machines
Enumerability
Arun-Kumar S
:
Theory of Computation-I
Lecture notes (Recursive Function Theory)
Gordon M
:
Introduction to Functional Programming
,
Lecture notes 1996 (Annotated 2008)
Minsky M
:
Computation: Finite and Infinite Machines
, Prentice-Hall 1967.
Kozen D
:
Automata and Computability
, Springer-Verlag 1997
Cutland N
:
Computability: An Introduction to Recursive Function Theory
, Cambridge University Press 1980
Boolos G S, Jeffrey R C
:
Computability and Logic
, Cambridge University Press 1989.
Davis M D, Weyukar E J
:
Computability, Complexity, and Languages
, Academic Press 1980.
Hopcroft J E, Ullman J D
:
Introduction to Automata Theory, Languages and Computation
, Addison-Wesley 1979.
S. Arun-Kumar
Amusement Park
