COVID-19 Update
The health and safety of our community is of the utmost importance to us at UMass Boston. We are closely monitoring the evolving COVID-19 (Coronavirus) situation. Due to concerns, UMass Boston is currently operating online only. Many answers about the campus's response to the coronavirus can be found in our special coronavirus web section.

In addition please subscribe to our classmembers list for continued updates on courses and more. If you have any inquiries please contact us at csinfo@umb.edu.

Click here for a message from the CS Chair, Marc Pomplun as of March 20, 2020.

HomeAcademicsCourses → CS420

Introduction to the Theory of Computation (3 credits)

Introduction to theoretical aspects of computing including models of computation, inherent limits on computation, and feasible computation. Topics studied will include definition of computable functions (recursive functions, functions computable by Turing machines, functions computable in a programming language), insolvability of the halting problem and related problems, the classes P and NP, finite automata, and context-free grammars.

Note

This course is required for all computer science majors who took CS 220/CS 320L during fall 1989 or later. It may be used as a theoretical elective by other computer science majors.

Textbook(s)
Title: Introduction to the Theory of Computation
Author(s): Michael Sipser
Publisher: Course Technology
Edition: 3rd
ISBN: 113318779X

Pre-requisites

CS 220/CS 320L


This page was last modified on September 03, 2019
© 2019 University of Massachusetts Boston

Template by OS Templates