Course: CSE 303: Introduction to the Theory of Computation

State University of New York at Stony Brook, Summer 2023

Prof. Pramod Ganapathi
Office hours: Tuesday 07:30 am - 10:30 am via Zoom
Google Sheets link
CEAS Free Tutoring Service Schedule

Course Description
In this course, we will learn the mathematical theory of computation, computers, algorithms, and complexity. In this course, we will learn what can be computed (i.e., capabilities) and what cannot be computed at all (i.e., limitations) on a computer. We also learn, if something can be computed, how efficiently can it be computed (i.e., complexity). The topics covered include:
  • Computation models (finite automata, pushdown automata, and Turing machines)
  • Grammars accepted by different computation models (regular grammars, context-free grammars, and unrestricted grammars)
  • Languages accepted by different computation models (regular languages, context-free languages, and Turing-acceptable languages)
  • Turing-complete systems
  • Algorithmically unsolvable problems
  • Algorithmically hard problems
C or higher: CSE 214 and 215 and CSE major.
Course Outcome
At the end of the course, the students should have the following knowledge and skills:
  • Understand the motivations behind and differences between various computation models
  • An ability to determine the algorithmic complexity or algorithmic impossibility of a given computational problem
  • An ability to determine the simplest computation model to solve a given computational problem
Other Resources
CSE 303 course requirements and grading are as follows:
  • Homeworks: 40%
  • Project: 10% (presentation: 5%, work and writing: 5%)
  • Midterm: 20%
  • Final: 30%
  • Bonus points: up to 5% depending on creativity
Homework assignments will be posted on Brightspace:

Academic calendar
Class Schedule
Optional Learning Materials
2 sessions Introduction (Course Info, Motivation, Course Overview) [PDF] [M, Ch. 1]
6 sessions Computation Model → Finite Automata
Grammars → Regular Grammars (or Type-3 Grammars)
Languages → Regular Languages
[PDF] [M, Ch. 2, 3]
6 sessions Computation Model → Pushdown Automata
Grammars → Context-Free Grammars (or Type-2 Grammars)
Languages → Context-Free Languages
[PDF] [M, Ch. 4, 5, 6]
1 session Midterm Exam Time: Thursday July 20, 6-7:30 pm, Venue: Office hours Zoom link
5 sessions Computation Model → Turing Machines
Grammars → Unrestricted Grammars (or Type-0 Grammars)
Languages → Turing-Semidecidable Languages
[PDF] [PDF] [M, Ch. 7, 8] Morten Tyldum's The Imitation Game, Lambda Calculus
5 sessions Algorithmically Solvable/Unsolvable Problems [PDF] [M, Ch. 9, 10] Undecidability: (Part 1, Part 2, Part 3), Halting Problem, Busy Beaver Problem, Chomsky Hierarchy, Self-replicating program
1 session Algorithmically Hard Problems [PDF] [M, Ch. 11] Erik Demaine's Complexity I, Complexity II, Michael Sipser's P vs. NP Problem, Avi Wigderson's P vs. NP Problem, Complexity Zoo
1 session Final Exam Time: Thursday August 17, 6-8:30 pm, Venue: Office hours Zoom link

Academic Integrity
Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at
Student Accessibility Support Center
If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, ECC (Educational Communications Center) Building, Room 128, (631) 632-6748, or at They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and the Student Accessibility Support Center. For procedures and information go to the following website: and search Fire Safety and Evacuation and Disabilities.
Critical Incident Management
Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.