Course: CSE 303: Introduction to the Theory of Computation

State University of New York at Stony Brook, Summer 2026

Classes	Asynchronous online via Google Drive (Theory of Computation) using @stonybrook.edu email account.
Instructor	Prof. Pramod Ganapathi Office hours: Mo 10:00-01:00 PM via TBD
Tutoring	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
Prerequisites	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
Textbook	[R] Automata, Computability and Complexity: Theory and Applications. Elaine Rich. [LP] Elements of the Theory of Computation. Harry R. Lewis and Christos H. Papadimitriou. 2nd Edition. [M] Introduction to Languages and the Theory of Computation. John Martin. 4th Edition.
Grading	CSE 303 course requirements and grading are as follows: Homeworks: 40% Midterm: 30% Final: 30%
Homework	Homework will be posted on Brightspace. Homework must be written on plain sheets of paper, scanned using a good scan app, and a single scanned PDF must be submitted on Brightspace. The PDF must have the student ID as the file name. Late submissions will not be graded for any reason (including oversleeping, forgetting, PC issues, technical issues, Brightspace issues, traveling, etc), except extenuating situations. It is strongly recommended to submit at least one version three days before the deadline. A student can submit an infinite number of versions of the answer sheets PDF to the Brightspace. We only evaluate the last/final version of the solutions PDF uploaded on Brightspace before the deadline. Students who submit the first version of their homework at the exact deadline or after the deadline (even a nanosecond later), will receive 0. Because, we do not consider the time at which a homework was submitted by the student, we consider the time at which the homework was successfully up on Brightspace (with all pages in human-readable form) and it takes a few seconds/minutes to upload on Brightspace. If Brightspace flags the homework as late, it is late. It is the student's responsibility to verify whether the document was successfully submitted on Brightspace or not. Hence, it is strongly recommended to submit the homework multiple times starting from a few days before the deadline. Grade/regrade requests deadline is 1 week after getting the homework/exam results on Brightspace. Any grade/regrade requests after this deadline will not be considered. Each student is assigned a TA. The grade/regrade requests must be made only to the assigned TA.
Makeup Exams	The exams will be closed-book, closed-notes, closed-computers, and closed-calculators exams. The exams will be in person and will be proctored. Makeup exams will not be given for any reason (including oversleeping, forgetting, PC issues, technical issues, Brightspace issues, traveling, etc), except in the cases of medical emergencies (with documentation -- e.g. USA doctor's non-electronic signed note with all contact details/information stating that the student was ill and unfit to take the exam) and on the discretion of the instructor based on a case-by-case basis; student participation in university sponsored events (with documentation); and religious absences (with documentation). Students who miss an exam for an undeniably valid reason need to take a make-up exam; specific arrangements will be made on a case-by-case basis. Students who miss an exam must either give advanced notice (e.g. broke leg the previous day) with evidence or must report as soon as possible (e.g. met with an accident or medical emergency) with evidence. Students who miss exams for unimportant reasons (oversleeping, technical issues, transportation problems, family/friend functions, etc) will not be given make-up exams. Students are expected to abide by all standard examination rules and obey instructors/TA's at all times during the exams.
Attendance	Students are expected to attend every class, report for examinations and submit major graded coursework as scheduled. If a student is unable to attend lecture(s), report for any exams or complete major graded coursework as scheduled due to extenuating circumstances, the student must contact the instructor as soon as possible. Students may be requested to provide documentation to support their absence and/or may be referred to the Student Support Team for assistance. Students will be provided reasonable accommodations for missed exams, assignments or projects due to significant illness, tragedy or other personal emergencies. In the instance of missed lectures or recitations, the student is responsible for reviewing posted slides, reviewing recorded lectures, seeking notes from a classmate, etc. Please note, all students must follow Stony Brook, local, state and Centers for Disease Control and Prevention (CDC) guidelines to reduce the risk of transmission of COVID.

Academic calendar

Lectures	Class Schedule	Slides	Study	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 June 25, 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: Wednesday July 15, 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 https://www.stonybrook.edu/commcms/academic_integrity/.
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 sasc@Stonybrook.edu. 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: https://ehs.stonybrook.edu/programs/fire-safety/emergency-evacuation/evacuation-guide-people-physical-disabilities 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.