Description:

Introduces the abstract notions of machine computation for honors students. Includes finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Explores what can and cannot be computed by considering various models of computation including Turing machines, recursive functions, and universal machines.

Course Outcome:

• 1. An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.

  2. An ability to define, use, and convert between abstract machine models and formal languages.

  3. An ability to apply abstract models of computation to analyze the power and inherent limitations of algorithms.

Tentative Lesson Plan (Sipser's book):

• Finite automata, non-determinism, regular languages, pumping lemma. [Chap. 0--1] (Week 1-4)

• Context-free languages, grammars, pushdown automata [Chap. 2] (Week 5-6)

• Turing machines, decidability, reductions, computability [Chap. 3--5] (Week 7-12)

• Complexity theory, NP Completeness [Chap. 7] (Week 13- 16)

CSE150 or CSE215; AMS 210 or MAT 211; Computer Science Honors Program or Honors College or the WISE Honors program or University Scholar.

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

• John Watrous lecture notes on Introduction to the Theory of Computing (https://cs.uwaterloo.ca/~watrous/ToC-notes/)

The grading will be based on the following criteria: 

• Midterm - 30%

• Final - 35%

• Eight short 10-minute in-class quizzes - 25% (Best 5 count, 5% each)

• Scribe assignment - 10%

For each of the five quiz scores counted toward the course grade, the student's final-exam percentage will replace any lower or missing score.

Support Services

• If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC (Educational Communications Center) Building, room 128, (631) 632-6748 or at sasc@stonybrook.edu. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.
  
  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. Faculty are 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.
  
  AI Use Policy:

• We will follow the policy of the department: https://www.cs.stonybrook.edu/students/Policies/aiusage
  
  

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 Judicial Affairs 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.
  
  Final Grade:
  
  Final grades will be based on how well you've learned the material. Letter grades and grading details (like cutoffs or curves) won't be disclosed or discussed. Please don't ask for comparisons or special treatment. Needing a higher grade or being close to a cutoff might not affect your result. Grades are final and any requests for grade bumps or exceptions will be ignored.
  
  

• Communication Policy:
  
  The preferred way to communicate is through the course discussion forum piazza - it is the quickest since both the teaching team and your classmates can respond. You're also encouraged to stop by office hours for one-on-one help. If you need to email the instructor or the TA, only use the official email addresses shared in class or on the course website, and always include a clear subject line starting with "[CSE 350]".