Classes 
Asynchronous 

Instructor
 Prof. Pramod Ganapathi Office hours: Tuesday 07:30 am  10:30 am via Zoom 
TA's
 Google Sheets link 
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:


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:

Textbook 

Other Resources 

Grading 
CSE 303 course requirements and grading are as follows:

Homework 
Homework assignments will be posted on Brightspace: https://it.stonybrook.edu/services/brightspace. 
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 Type3 Grammars) Languages → Regular Languages 
[PDF]  [M, Ch. 2, 3]  
6 sessions  Computation Model → Pushdown Automata Grammars → ContextFree Grammars (or Type2 Grammars) Languages → ContextFree Languages 
[PDF]  [M, Ch. 4, 5, 6]  
1 session  Midterm Exam  Time: Thursday July 20, 67:30 pm, Venue: Office hours Zoom link  
5 sessions  Computation Model → Turing Machines Grammars → Unrestricted Grammars (or Type0 Grammars) Languages → TuringSemidecidable 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, Selfreplicating 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, 68: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) 6326748, 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/firesafety/emergencyevacuation/evacuationguidepeoplephysicaldisabilities 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 FacultyEmployee Handbook. 