CSE 617 – Theory of Comuptaion

CSE 617 : Theory of Computation

Credits: 3 hours/Week

Instructor: Rokan Uddin Faruqui. email: rufaruqui AT cu.ac.bd 
Classes begin on January 24, 2017 at 9:50am in ITB Room # 311
Class Schedule: Monday    10:40 - 11:25 am
                Wednesday 09:50 - 11:25 am

Course Outline

Weeks Topics Assignments Resources
Week 1 (Jan. 24-25) Introductory lecture on Automata, Complexity, Computability,Definitions, Theorems, Proofs, Types of Proofs. Reading Assignments: Set, Function, Relation, Predicate, Boolean Algebra.

Book: Sipser, Chapter 0

Week 2 (Jan. 30) Types of Proofs. Regular Language, Finite Automata, Formal Definition of FSM Reading Assignments:

Book: Sipser, Chapter 1

Week 3 (Feb. 6 and 8) Chapter 1, Theorem 1.25
Book: Sipser, Chapter 1


Text Books

  1. Introduction to the Theory of Computation (third edition), Michael Sipser, Publisher: Cengage Learning, 2012.
  2. An Introduction to Formal Languages and Automata (third edition), Peter Linz, Publisher: Jones and Bartlett, 2001.


  1.  Introduction to Languages and the Theory of Computation. John Martin,  McGraw-Hill, NY, 1991.
  2.  Automata theory, languages, and computation.” Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. International Edition 24 (2006).