| Class meeting | 2:00-3:15 TTh Austin 304 |
| Instructor | Karl Abrahamson |
| Office | Austin 233 |
| Office hours | MW 11:00-12:30, TTh 11:00-12:00 or by appointment |
| Phone | 328-1879 |
| karl@cs.ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/4602/fall02/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Text: | Introduction to the Theory of Computation 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, as well as some general methods of computation and a collection of problems that are known to be difficult or impossible to solve.
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 (12% each), a comprehensive final exam (20%) and homework assignments (20% total).
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 |
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 (ADA). Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Brewster A-114, to verify the disability before any accommodations can occur. The telephone number is 252-328-6799.