CSE 596     Course Information     Fall 2012


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

TA:  Andrew Hughes    203 Davis (Cobham Lab)         ahughes6@buffalo.edu


Office Hours:
Regan: Mondays 2--4pm, Tuesdays 1--3pm
Hughes: Thursdays 11am--noon, Fridays 11:30am--12:30pm; in Davis 302.

Hughes also leads a Weekly Review Session, Mondays 11:00--11:50am, in Clemens 19, as an add-on to TA office hours.


Lectures and Recitations: (LEC) MWF   1:00pm-1:50pm   in Norton 218


Assignments

Assignment 1, due in class Wed. Sep. 12.
Assignment 2, due at my office (326 Davis) or mailbox by noon on Thu. Sep. 27. Answer Key.
Assignment 3, due in class Wed. Oct. 3. Answer Key.
Assignment 4, due in class Wed. Oct. 17. Answer Key
Assignment 5, due in class Wed. Oct. 24. Extended to Fri. Oct. 26. Answer Key
Assignment 6, due in class Fri. Nov. 2. Answer Key
Assignment 7, due in class Fri. Nov. 9. Answer Key
Assignment 8, due in class Wed. Nov. 28. Answer Key
Assignment 9 (the last), due in class Fri. Dec. 7. Answer Key


Required Reading

  1. Computability and Complexity Theory (2nd ed.) by Professors Steven Homer and Alan L. Selman, which has been used in CSE596 the past twelve years. If you have the 1st ed., please see me for some updates.

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

  3. Chapters 27 and 28 of the CRC Handbook on Algorithms and Theory of Computing , co-authored by me with Professors Eric W. Allender and Michael C. Loui---given out in class on 10/17.

  4. Handouts on diagonalization, the Myhill-Nerode Theorem, a programmer's view of the S-m-n and Recursion Theorems, and the arithmetical hierarchy. The last was given out on 10/17; the proof of Theorem 4.1 will be skimmed.

  5. Excerpts from the seminal paper by Alan Turing, On Computable Numbers... will be read in Week 1, as a way of observing the Turing Centenary. See also the Turing Page and especially check out the Turing Scrapbook.

  6. The newsgroup sunyab.cse.596 . This will tend to have "dynamic" information, e.g. helps on problem sets, whereas the course webpage (tba, after I experiment with a new LaTeX-to-HTML translator) will tend only to have ``static'' info. For especially important info-such as ``bugs'' in problems (they do happen :-() or deadline alterations-I will send a ``heads-up'' e-mail to the whole class.

  7. The Java application (not an applet) Turing Kit , authored by former undergraduate Mark D. Grimaldi under my supervision. It is available in projects/regan/TM2/.../ More information about it will be posted shortly-it will only be used in the early weeks of class.

  8. No "course blog", but readings may be given on the blog "Gödel's Lost Letter and P=NP" (rjlipton.wordpress.com) which I co-manage.


Reserve List (SEL 2-hr. reserve. Not required. May be useful for background. From Week 2 onward.)

  1. J. Hopcroft and J. Ullman, Introduction to Languages, Automata Theory, and Computation , Addison-Wesley, 1979. The classic text. This course will mostly parallel the material in chapters 7-13 of this text; most of chapters 1-6 is assumed background.

  2. H. Lewis and C. Papadimitriou, Elements of the Theory of Computation , Prentice-Hall, 1981. Has more examples and illustrations and neat little tidbits than Hopcroft-Ullman.

  3. N. Cutland, Computability , Cambridge University Press, 1980. A short-but-comprehensive and crystal-clear treatment of computability theory, the main topic of the first part of the course. [if I can locate my copy]

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:   36%
Prelims: 24%
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.

My (KWR) general policy is that late work is not acceptable . In return, you get an answer key shortly afterward, and a quick turnaround of graded work before the next problem set is due. In an exceptional situation, you may contact me beforehand. All submissions must have your name and recitation number . Hardcopy submissions with more than one sheet must be stapled together .


Approximate Course Calendar

The plan is to cover Homer-Selman, chapters 1--3 on Computability Theory, in the first six weeks, and then cover Complexity Theory using Homer-Selman and my book chapters in parallel. ``Stereo is better than mono.'' I will give indication from week to week of 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. The intended coverage is Homer-Selman chs. 1--6 and much of 7, and Chs. 27 and 28 of Allender-Loui-Regan.