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
Sample Prelim I, from Fall 2022
Sample Prelim II, from Fall 2022
Sample Final Exam, from Fall 2022
These will mostly follow the 2022 sequence shown below. The main changes will be:
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.
Sample Prelim II, from Fall 2021
Sample Final Exam, from Fall 2021
Required Reading (combined from multiple texts, no textbook to purchase)
The previous required reading agenda had the three-part structure of an insect: First these notes (original smaller-font version) scribed by Arun Debray from lectures by Ryan Williams at Stanford. (They 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.) They will lead into...
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.
Also: 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.
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.
java -cp TKIT70.jar Main
Open the file DragonSL.tmt and then do View--Auto Resize to get a bigger canvas. You can also load a different color scheme and much else.
Optional Reading
Computability and Complexity Theory (2nd ed.) by Steven Homer and Alan L. Selman. This textbook used in many previous years is now optional.
Handouts on a programmer's view of the S-m-n and Recursion Theorems, and the arithmetical hierarchy.
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.