| Instructor: | Karl Abrahamson |
| Office: | Austin 233 |
| Office hours: | MWF 1:00-2:00, TTh 9:00-10:00, MW 8:00pm-8:30 |
| Phone: | 328-1879 |
| Email: | karl@cs.ecu.edu |
| Course web page: | www.cs.ecu.edu/~karl/4602/fall00 |
| My web page: | www.cs.ecu.edu/~karl |
| Text: | Introduction to the Theory of Computation by M. Sipser |
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.
The prerequisite for this course is Math 2427 or equivalent knowledge of discrete mathematics. 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.
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 by 90% for an A, 80% for a B, 70% for a C and 60% for a D. Those cutoffs will not be raised.
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.
Material for this course is posted on page http://www.cs.ecu.edu/~karl/4602/fall00.