| Course Title: Theory of Computation |
| Start Date: 09/03/2025 End Date: 12/16/2025 |
| Term: Fall Semester 2025 |
| Description: Are there any limits to what computers can do? Does the answer to this question depend on whether you use a PC or a Mac? Is C more powerful than Python? This course explores these questions by investigating several models of computation, illustrating the power and limitations of each of these models, and relating them to computational problems and applications. Topics include finite state automata, pushdown automata, grammars, Turing machines, the Halting Problem, and NP-completeness. |
| Distribution(s): II - Math & Sciences |
| Academic Level Of Course: Undergraduate | Credits:4.00 |
| Faculty | Phone | Email address |
| Audrey Lee St. John | 413-538-2509 | astjohn@mtholyoke.edu |
| Meeting Dates | Method | Meeting days | Meeting times | Building name | Room | Frequency |
| 09/03/2025 - 12/16/2025 | Lecture | Tuesday and Thursday | 09:00AM - 10:15AM | TBA | TBA | Weekly |
| Requisite Courses | ||
| Prereq: COMSC-205 and MATH-232. | Take previously | Required |
| Comments |
| Additional Comments |
| This 3-minute student-created video gives an overview: https://www.youtube.com/watch?v=SV57Yv8BXBc. |
| Course Tags | ||
| NXDTA0001 | NXDTA: Nexus in Data Analytics and Society | This course is approved for the Data Analytics |
| Cross-listed Sections |
| None |
| Course Availability | ||||
| Section status: Waitlisted | Capacity: 14 | Enrollment: 18 | Available: 0 | Waitlist: 7 |
BOOK INFORMATION
| Book List | Required | Publisher Full Price |
| Title: Introduction to the Theory of Computation Author: Sipser, Michael Copyright: 2005 Edition: 2 Volume: ISBN: Publisher: Course Technology |
Required | 167.95 |
| Additional Book Comments |
| This is NOT the complete book list for this class. |