CSE 491/596     Course Information     Fall 2021

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

KWR's Office Hours:

Lectures (LEC) MWF   1:50pm-2:40pm   in Clemens 120

Fall 2021 Assignments

Sample Prelim II exam, from Fall 2020

Lecture Notes for Fall 2021

(will mostly follow Fall 2020 as below)

Syllabus from Fall 2020, with change involving recitations that was agreed in class in 2020. For 2021, the handling of recitations (which are nominal) vis-à-vis office hours will take a little more time to determine---they do not meet in week 1 in any event. This printable version mostly replicates material here but says more about the material and its philosophy, including the ABET objectives for CSE491.

Piazza Page for Fall 2021

Note (which was already written in Fall 2018): The orientation of the course is changing from prior emphasis on formal reasoning and rigor for general doctoral study to greater emphasis on algorithmic content. It may later evolve back into the undergrad+grad 4xx/5xx format that existed when I came in 1989. The change away from the previously-used textbook is part of this evolution. The below-linked notes by Arun Debray from Stanford's undergrad course led by Ryan Williams (about whom, see this blog article by me) share many of my own preferences: Myhill-Nerode Theorem, streaming algorithms, many-one reductions earlier rather than later, Gödel's Incompleteness Theorems included and handled simply, quick road to NP-completeness. The change is also partly reflected in my slides for a 20-hour course given at the University of Calcutta in August 2016.

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

  1. The "backbone" of the course (except for quantum computing material at the end) will be these notes (original smaller-font version) scribed by Arun Debray from lectures by Ryan Williams at Stanford. They will lead into...

  2. Chapters 27 and 28 (earlier versions) of the CRC Handbook on Algorithms and Theory of Computing , co-authored by me with Eric W. Allender and Michael C. Loui. Note these have "2up" versions, which save paper. Nicely printed hardcopy versions of these materials are available on request.

  3. Extra material for Weeks 2--3: Lecture Notes on Finite Automata by Dr. Mitsunori Ogihara, University of Miami. DFAs, NFAs, Regular Expressions. Slides for visualizing DFAs, collected by Andrew Hughes. NFA slides too.

  4. Supplementary notes by John Watrous on undecidability and reductions (note---he updated the links on 10/19/20 but they have the same lecture numbers): lecture 15, lecture 16, lecture 17.

  5. Handouts on diagonalization, the Myhill-Nerode Theorem, and later subjects as warranted---including the basics of quantum computing.
  6. New 11/2/18: Handout on complexity-class relationships, for Week 11 lectures.
  7. "Turing Kit" Simulator, designed by Mark D. Grimaldi for CSE396 in 1997.

Lecture Notes From Fall 2020

(much of it will be followed as-is)

Assignments in Fall 2020 (answer keys viewable on Piazza)

Lecture Notes From 2018

(includes some office-hour review sessions)

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: (In Fall 2020, material and points will be scaled back for online exams)


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.

The weighting of grades in Fall 2019 was:

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

The currently-intended weighting in Fall 2020 is:

Homework: 40%
Prelims: 18%
Final: 27%
Tutorial: 15%

In the British tutorial system, a common activity is each of typically 3 students presenting a solved problem for 15 minutes (or more time every other week) and/or everyone answering followup questions about homeworks.

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.