CS 515, Theory of Computation

Spring 2016 - 2017

Instructor

      Purandar Bhaduri, ext: 2360 (email: pbhaduri)

Teaching Assistants:

Ramanuj Chouksey (email: r.chouksey)

Textbooks

Michael Sipser, Theory of Computation, Cengage Learning, India Edition, 2008/2014.

 Other Sources

1. Lecture Notes and Slides by Gul Agha and Mahesh Viswanathan for CS 373 at UIUC.

2. Lecture Slides by Eli Upfal for CS 152 at Brown University.

3. Lecture Slides by Ryan Williams for CS 154 at Stanford.

Evaluation

Assignments 15%

Midsem                         35%

Endsem                         50%

Midsem Solutions

Endsem Solutions

Homework

1. HW#1: Exercises and problems 1.5(e), 1.6(l), 1.12, 1.29(b) and 1.32 from here. Due date: Friday, 03 February 2017.

2. HW#2: Problems 2.25, 2.30(a), 2.31, 2.39 and 2.44 from here. Due date: Wednesday, 22 February 2017.

3. HW#3: Problems 4.20, 4.26, 5.21, 5.22 and 5.32 from here. Due date: Wednesday, 29 March 2017.

4. HW#4: Problems 7.12, 7.20, 7.27, 7.29 and 7.34 from here. Due date: Monday, 24 April 2017.

Homework Policy

Late assignments would be penalised by deducting (10 × no. of days of lateness) % of the marks. Any form of copying will incur zero marks.

back to homepage