CSE 350: Theory of Computation: Honors (Fall 2022)


1   Class Meetings

2   Course Description

An introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines.

3   Course Learning Outcomes

At the end of this course, the students should have an understanding of different models of computation, their strengths and limitations, as well as why some problems cannot be solved by a computer. The students should have the ability to argue about the the correctness and complexity of a computational algorithm as well as perform reductions between different computational problems.

4   Prerequisites

C or higher: CSE 215/150 or CSE 214/160

5   Textbook

Introduction to the Theory of Computation, 3rd edition, by Michael Sipser

6   Grading

The grading will be based on the following examinations and assignments:

Note the following:

7   Tentative Examination Dates and Times:

8   Tentative Class Schedule

Week Lecture Topics Assignments
1--4 Finite automata, non-determinism, regular languages, pumping lemma. [Chap. 0--1] HW1
5--6 Context-free languages, grammars, pushdown automata [Chap. 2] HW2
7--12 Turing machines, decidability, reductions, computability [Chap. 3--5] HW 3, 4 + Midterm
13--15 Complexity theory, NP Completeness [Chap. 7] HW 5, 6

9   Student Accessibility Support Center Statement

If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (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.

10   Academic Integrity Statement

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. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty please refer to the academic judiciary website at http://www.stonybrook.edu/commcms/academic_integrity/index.html

11   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. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.