CSE 396

Introduction to the Theory of Computation

Spring Semester 2009

Professor Selman; Office: Bell 223; selman@cse.buffalo.edu; 645-3180, ext. 104

T R 12:30 PM—1:50 PM, 214 Norton

Office hours: I will announce office hours as soon as I know my complete schedule.

TAs will assist and lead the recitation sections.

Recitation sections: You must be enrolled in and attend one of the recitation sections. Recitations sections will meet weekly beginning Thursday, January 22, the second week of classes. (Classes do not meet Jan. 19.)

Prerequisite: You must have a C- or higher in CSE 250. This is absolutely critical. You must not take this course if you have not satisfied the prerequisites.

Textbook: Michael Sipser, Introduction to the Theory of Computation, Second Edition, 2006

Grades will be based on two exams during the semester, quizzes, and a cumulative final exam. There are no “extra credit” assignments.

Exam 1 20%, Exam 2 20%, Quizzes 20%, Final Exam 40%.

Exam 1 Tuesday, February 17

Exam 2 Tuesday, March 31

Final Exam: Do not plan to travel home at the end of the semester until final exam week is over. I do not know when the final exam for this course will be scheduled, and I will not give an early final exam to any student.

Quizzes

#1 Thursday, January 22	#6 Thursday, March 19
#2 Thursday, January 29	#7 Thursday, April 9
#3 Thursday, February 5	#8 Thursday, April 16
#4 Thursday, February 26
#5 Thursday, March 5

There are a total of eight quizzes. Each quiz takes 10 to 20 minutes. I will drop the two lowest grades and count the remaining six.

Quizzes are not given automatically at either the beginning or at the end of a class period. It is your responsibility to be in class when a quiz is given. If you miss a quiz, that quiz becomes one of your two lowest quizzes (so no penalty ensues). However, if you should miss three or more quizzes, these will count as zero. No make-up quizzes will be given. Do not request a make-up if you miss a quiz.

To repeat: I will drop the two lowest grades and only the two lowest grades. There are no reasons for dropping more than the two lowest grades.

All exams and quizzes are closed book, closed notes, and open mind!

Attendance: Regular attendance is required. You must be on time. It is not acceptable to come to class twenty minutes late. You must attend the recitation sections also. (Please stay home if you have the flu or are otherwise sick.) You might want to know that there is a strong correlation between regular attendance and performance on the final exam.

You are not required to attend class on days listed in the university calendar as major religious holy days (although I assume that you practice at most one religion).

Homework: You learn this subject by studying your class notes, reading the textbook, and doing homework. Success on the quizzes and exams depends largely on skill with homework. TAs will be available to help you with homework problems and they will review homework solutions in your recitation sections. Also, they will attempt to correct your homework solutions.

I will collect homework solutions every Thursday in class, and plan to return solutions to you the following week. Please note that this activity is to help you learn the material only, and homework solutions will not count toward your final grade. However, this activity is important. Students who do not regularly hand in homework assignments and attend recitations do not perform well in this course. I urge you to do the homework assignments. You cannot learn the material by attending class only.

Homework assignments are due in class every Thursday. Hand in the assignments that are given the week before. We will not accept late assignments. Please remember to print your name on every page that you hand in. Also, please print neatly—the TAs cannot correct what they cannot read—and get into the habit of using a sharp pencil for your work. A ballpoint pen is not appropriate for mathematical or technical work.

What homework is due on Thursday? This is the question we receive most often. Do not ask this question because it is your responsibility to know the answer. I will assign homework exercises as I cover the material. You will write the assignments down, keep a record, and hand in the solutions the following week.

It is not always possible for the TAs to correct your written assignments because of their other course responsibilities, and because they are students also. However, they will make every effort to do so and they will make sure that you have access to the correct solutions.

Academic Honesty: The Department's policy statement is available at

http://www.cse.buffalo.edu/academics-academic_integrity.shtml.

With regard to homework exercises, let me note again that they do not count toward your grade, with the exception that you must work at them and hand in your best effort. All of the quizzes and exams that you hand in must be the result of your own independent effort. Work that you claim to be yours must be yours. If one student permits another student to copy, then both are equally guilty. All instances of academic dishonesty will result in an F in this course. There are no minor infractions. Unfortunately, students have failed this course because of copying from another student while taking a quiz or exam, or by changing an answer on a returned quiz or exam, and then asking for additional points.

Time Management: A typical course is designed to require three hours outside of class for each hour spent in class. Thus, a four-hour class is supposed to fill up 16 hours of your week. If, for example, you are carrying a 16-credit course load, then your total time obligation is 64 hours each week. If you are taking courses that require you to write large programs, then, as you probably already know, these may require even more time. If your academic schedule requires 64 hours each week, you need to average nine hours each day. That does not leave much time for anything else. Therefore, if, for example, for economic reasons, you need to work during the academic semester, seriously consider lowering your academic workload accordingly. Otherwise, something will suffer, and the something that suffers usually is academic performance.

Incompletes (the grade of “I”) will not in general be given. This is reserved for the rare circumstance that prevents a student from completing the work in the course. University and Department policy dictates that an “I” can be given only if both of the following conditions are met: (i) Only a small amount of work remains, such as the final exam and one or two assignments, and (ii) the student has a passing average in the work completed. In such a circumstance, the student will be given instructions and a deadline for completing the work, which is usually no more than 30 days past the end of the semester.

Incompletes cannot be given as a shelter for poor grades. It is the student’s responsibility to resign from the course in a timely manner if doing poorly. The last day to resign is Friday, March 27.

Course Topics: In this course we will study several of the more important and exciting intellectual achievements of the twentieth century:

Theory of Computation is concerned with the following kinds of questions: What features are necessary in general models of computation? What are the limitations of computers? What problems can computers not solve? What problems can be efficiently computed? What problems cannot be efficiently computed?

Automata Theory is concerned with simple mathematical models of computation. We are concerned with studying the relative power of different models, and with robustness of different models. Automata theory is used in compiler design, operating systems, AI, and circuit design. In courses in those subjects you may concentrate on "How to do something" or on "how to design something." Here we are concerned with what can and cannot be done with different models.

Formal Language Theory is concerned with the formal manipulation of symbols. All the rules for languages are explicitly stated in terms of what strings belong to a language. No semantic meaning is attached. We are concerned with syntax. This is very different from grammatical studies of natural languages—but forms a basis for some studies in that direction also. A crucial question in formal language theory is what kind of computational effort is required to recognize what kinds of formal languages. Thus the two subjects, Automata Theory and Formal Language Theory, are inextricably bound.

Complexity Theory is concerned with providing quantitative measures on the resources needed to solve computational problems. This is the branch of Theory of Computation that addresses the questions about which problems can be efficiently solved and which cannot be efficiently solved. In particular, we will learn about the complexity classes P and NP and about NP-complete problems.

Newsgroup You need to have an account on a UNIX machine. Get into the practice of reading the newsgroup sunyab.cse.396. We will keep you informed of course business this way.

Webpage The address for the course page is

http://www-local.cse.buffalo.edu/courseweb/cse396/