Lecture: Models of Computation

BTech(ICT), semester VII, elective

Monsoon semester, 2017-18

Course Code: CSC520

Instructor: Barbara Morawska

Email: barbara.morawska@gmail.com

Office hours: room 238, Wed. 9:45 - 11:45

Lecture time:

  • Monday, 9:45 - 11:15 AM
  • Thursday, 9:45 - 11:15 AM

Location:

SEAS, room 204

Course description:

This course gives an introduction to models of computation that include deterministic and non-deterministic finite automata, pushdown automata, Turing machines, decidable and undecidable computation problems, alternating Turing machines. Topics will include some aspects of computational complexity.

Reference book:

Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2013

Grading scheme:

  • Problem solving 30% (weekly assignments, presentation of solutions)
  • Midterm exam 30%
  • Final exam 40%