Instructor:
Dr. Kenneth W. Regan 326 Davis
Hall 645-4738 regan@buffalo.edu
Office Hours:
Regan: Mon. 4--5pm, Tue. 2--3pm, or knockable when in.
Lectures
(LEC) MWF 2:00pm-2:50pm in Norton 218
"Turing Kit" Simulator, designed by Mark D. Grimaldi for CSE396 in 1997. This appears to work again.
Note: 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. The change away from the previously-used textbook is part of this. Ideas for a new kind of textbook will be developed along lines already discussed in some posts this year on the Gödel's Lost Letter weblog. They are partly reflected in slides for a 20-hour course given at the University of Calcutta earlier in August 2016.
Assignment 1, due Wed. 9/21.
Assignment 2, due Wed. 9/28. Answer Key (handwritten scan)
Assignment 3, due Wed. 10/5. Answer Key (typeset)
Assignment 4, due Wed. 10/12. Answer Key
Assignment 5, due Wed. 10/26. Answer Key
Assignment 6, due Wed. 11/2. Answer Key
Assignment 7, due Friday 11/11. Answer Key
Assignment 8, due Friday 11/18. Answer Key
Assignment 9 (the last), due Friday 12/9.
Assignment 10 (extra option), due Monday 12/19.
Required Reading---some given out in class besides web-readable.
Selections from Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Cambridge University Press. Note the free pre-publication edition viewable there; we will use selections mainly from Part I.
Chapters 27 and 28 of the CRC Handbook on Algorithms and Theory of Computing , co-authored by me with Eric W. Allender and Michael C. Loui---already given out in class.
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.
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. The weighting of grades in this course shall be:
Homework: 30%
Prelims: 30%
Final: 40%
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 45% 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 problem sets. All
submissions will be in hardcopy.
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.