CSE 491/596     Course Information     Fall 2023


Instructor: Dr. Kenneth W. Regan   326 Davis Hall   645-4738   regan@buffalo.edu

Office Hours:

Lectures (LEC) MWF   2:00pm-2:50pm   in Norton 218

Fall 2023 Assignments

  1. Assignment 1, due Mon. 9/18, 11:59pm
  2. Assignment 2, due Fri. 9/29, 11:59pm
  3. Assignment 3, due Fri. 10/13, 11:59pm
  4. Assignment 4, due Wed. 11/1, 11:59pm
  5. Assignment 5, due Fri. 11/10, 11:59pm
  6. Assignment 6, due Tue. 11/21, 11:59pm
  7. Assignment 7, due Sat. 11/29 11:59pm

Sample Prelim I, from Fall 2022

Sample Prelim II, from Fall 2022

Sample Final Exam, from Fall 2022

Lecture Notes for Fall 2023

These will mostly follow the 2022 sequence shown below. The main changes will be:


Syllabus


Piazza Page for Fall 2023

Past Years' Materials

Most of these will be drawn on---a few skipped, per notes above. Additions and changes will be logged here. For instance, the 2022 first lecture was half like the 2019 and 2018 first lectures, way below; the other half centered on this Mult.-of-3 DFA picture. The other lectures followed Week 1 of Fall 2021 as below.

Note: Mon. Week 14 will have a visiting candidate lecture with revised notes, and both Week 13 lectures included some reference to the posted Week 13 notes from 2020-21.

Fall 2022 Assignments


Sample Prelim I, from Fall 2021

Sample Prelim II, from Fall 2021

Sample Final Exam, from Fall 2021



Required Reading (combined from multiple texts, no textbook to purchase)


Lecture Notes From Fall 2021 and 2020






Older Handwritten Notes: 2018

Lecture Notes From 2019


Optional Reading

  1. The course notes by Debray are based on the popular textbook whose first 7 chapters encompass our undergraduate CSE396 course: Introduction to the Theory of Computation by Michael Sipser. Links: brief MIT page, Amazon page.
  2. Computability and Complexity Theory (2nd ed.) by Steven Homer and Alan L. Selman. This textbook used in many previous years is now optional.

  3. Handouts on a programmer's view of the S-m-n and Recursion Theorems, and the arithmetical hierarchy.

  4. There may be some other optional elements, such as a forum (Piazza or newsgroup) and software to visualize Turing Machines (which needs update/repair). The weblog "Gödel's Lost Letter and P=NP" (rjlipton.wordpress.com), which I co-manage, may play some of the role of a ``course blog.''

Examinations:

Organization:

The course will be graded on a total-points system. Letter grades will also be given for individual exams and possibly some assignments, as a help in telling you where you stand, but only the point totals will have official significance.

Homework: 40%
Prelims: 24%
Final: 36%

I reserve the right to 5% leeway in weighting while assigning the final letter grade-this is most typically done for students who do markedly well on the final exam, when it may be treated as if it were worth 32% for that student. This will only be done to an individual student's advantage, and will have no effect on others' grades.


The homework will consist of weekly or bi-weekly problem sets. All submissions will be in PDF format via CSE Autolab---scanned or photographed PDFs of handwritten homeworks will be fine.

Problem set submissions must be your own individual work . No joint submissions will be accepted. In an early lecture I will explain the purpose of individual work, academic integrity, and the "qualitative" nature of exercises in this course. I will give guidelines on how work can be done and what can be discussed among you. Cheating will be punished as per department policy-in a graduate community this shouldn't have to be said, but alas it does. The Department's policy statement is available here.

My (KWR) general policy is not to implement a lateness-for-reduced-credit scheme. Instead I say that late work is not acceptable but extensions may be granted on request. Especially in smaller classes I am liberal with extensions, especially the 24-hour kind, but I still wish a request. In return, you get an answer key shortly afterward, and a relatively quick turnaround of graded work before the next problem set is due. In an exceptional situation, you may contact me beforehand.

Approximate Course Calendar

The plan is to cover finite automata and (non-)regular languages in the first three weeks (plus a day), then computability and undecidability through mid-term. The second half will feature computational complexity (using my chapters with Allender and Loui and Debray's notes as parallel texts): time and space complexity defined, why we emphasize P and NP, NPhardness and completeness, other salient complexity classes and the (known and unknown) relationships among them. Basics of randomized algorithms and quantum computing will round out the coverage. Homeworks or Piazza posts will give indication from week to week of exactly what to read. I cannot spell out a timetable in greater detail now because my lectures will adjust to the needs of the class. I welcome feedback to me personally.