| Class meeting | 10:00-10:50 MWF Bate 2015 | |||
|---|---|---|---|---|
| Instructor | Karl Abrahamson | |||
| Office | Sci&Tech C-113 | |||
| Office hours |
| |||
| Phone | 328-9689 | |||
| abrahamsonk@ecu.edu | ||||
| Course web page | www.cs.ecu.edu/~karl/4602/fall06/ | |||
| My web page | www.cs.ecu.edu/~karl/ | |||
| Text: | Introduction to the Theory of Computation (second edition) by M. Sipser |
The prerequisite for this course is Math 2427 or equivalent knowledge of discrete mathematics. You should have enough of a knowledge of computer programming to understand how simple programs are written.
This course is mathematical in nature, and you should have seen mathematical proofs before. You will be expected to produce your own proofs. We will go over proofs, and how to find and write them.
This is a course in the theory of computation. The fundamental question that we will ask is, "What is computable?" Some of the answers are surprising. For example, we will encounter some problems that are easy to express but that are so difficult, no computer program can be written to solve them.
We will also ask what can be computed efficiently. We will encounter problems that can be solved, but only by programs that run for a very long time.
Before asking what can be computed, we need a good understanding of the nature of computation. We will study simple models of computation, and explore what they can compute.
It turns out that a study of models of computation leads to the study of sets of strings, which are called languages. We will study various means of describing languages, some of them computational and some (at least apparently) not directly based on computation.
You should come out of this course with an improved understanding of the nature and limitations of computation. You should learn general methods of computation and a collection of problems that are known to be difficult or impossible to solve. You should be able to demonstrate the difficulty or unsolvability of some well-understood kinds of problems.
I will not take attendance. It is up to you to attend class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.
Those who choose not to attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that decision, however bad they are.
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already, and have done work of acceptable quality that it is realistic that you can pass the course.
Makeups of missed quizzes will only be offerred with a university-excused absence. If you miss a quiz without a university-excused absence, you will receive a grade of 0 for that quiz.
The grading will be on the basis of five quizzes (13-16% each), a comprehensive final exam (20-35%). (The quiz and final exam scores will be chosen within the given limits to give you your best score. In any event, all quizzes will have the same weight.)
Cutoffs for grades will tentatively be 90% for an A, 80% for a B, 70% for a C and 60% for a D. Those cutoffs will not be raised.
| Topic | Approx. Time |
|---|---|
| Preliminaries (Ch. 0) | 1.5 weeks |
| Finite state machines and regular languages (Ch. 1) | 3.5 weeks |
| Push-down machines and context-free languages (Ch. 2) | 2 weeks |
| General computation and computability (Ch. 3,4,5) | 4 weeks |
| Complexity of computation and NP-Completeness (Ch. 7) | 3 weeks |
Smoking is not permitted in classrooms. Please turn off telephones while in class.
Students are expected to abide by the university's Student Honor Code. The homework that you do is a critical part of your education. Each student is expected to do his or her own work. That does not mean you are not allowed to discuss your ideas with other students. Working in groups can be beneficial, and I encourage you to talk through ideas with other students. But outright copying is plagiarism, and is unacceptable. Students who copy other students' work, or who allow their work to be copied, or who copy their work from other sources, such as the internet, will receive no credit.
In the event of a weather emergency, information about ECU can be accessed through the following sources:
| ECU emergency notices | http://www.ecu.edu/alert |
|---|---|
| ECU emergency information hotline | 252-328-0062 |
East Carolina University seeks to comply fully with the Americans with Disabilities Act. Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Slay 138, to verify the disability before any accommodations can occur. The telephone number is 252-737-1016.