| Class meeting | Section 1: 9:00–9:50 MWF Austin 302 Section 2: 11:00–11:50 MWF Austin 307 |
|||
|---|---|---|---|---|
| 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/fall19/ | |||
| My web page | www.cs.ecu.edu/~karl/ | |||
| Text: | Introduction to the Theory of Computation (third edition) by Michael Sipser |
The prerequisites for this course are CSCI 2405 and 2530 or equivalent. You should have enough knowledge of computer programming to understand how simple programs are written and to understand how to convert an algorithm description into a program. There will be no programming assignments for this course.
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 in specific cases.
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 that 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. The following is an outline of this course.
After successful completion of this course, you should be able to do the following.
Analyze a given deterministic or nondeterministic finite-state machine and determine the language that it recognizes.
Design a deterministic or nondeterministic finite-state machine recognizing a specified language.
Analyze and design a regular expression specifying a given language.
Prove that a given language in not regular.
Perform an elementary closure proof for a given class of languages.
Explain the significance of Church-Turing Thesis.
Discuss the notion of universal Turing machine.
Define computability.
Recognize properties of reductions.
Use reductions to prove interesting results.
Describe a few computational problems that are not solvable by computers.
Define the complexity classes P and NP.
Define NP-complete problems.
List several NP-complete problems.
Explain the practical consequences of a problem being NP-complete.
Demonstrate the NP-Completeness of some computational problems by reduction.
Explain the significance of the P = NP question.
Students should both realize the importance of theory to the field of computer science and develop the abstract thinking needed to pursue it further as desired by them. This is more important than any of the specific outcomes listed above.
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 choice, however bad they are. If you are planning to graduate this accademic year, give careful thought before you decide not to attend class.
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you have completed work of acceptable quality and quantity that it is realistic that you can pass the course with a little more work.
There will be a midterm exam on each of the following dates.
You can bring one prepared 8.5x11" piece of paper, written on both sides, to each exam. You can write anything that you like on that paper. I will not collect it.
The final exam times are as follows.
| Section 1: | 8:00-10:30am, Wednesday, December 11 |
| Section 2: | 11:00-1:30, Monday, December 9 |
You can bring two prepared 8.5x11" pieces of paper to the final exam.
Grades will be computed as follows.
| Grading | |
|---|---|
| 5 midterm exams | 60–75% |
| A comprehensive final exam | 25–40% |
Percentages will be chosen on an individual basis from the indicated range to give you your best score. All midterm exams will have the same weight.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| Grade cutoffs | |||
|---|---|---|---|
| A | 93% | C+ | 76% |
| A– | 90% | C | 72% |
| B+ | 87% | C– | 68% |
| B | 83% | D+ | 64% |
| B– | 80% | D | 60% |
| D– | 56% | ||
Attend class. Arrive on time.
Do not bring distractions to class. If you read your email, listen to music, send and receive text messages or engage in other distracting activities during class, you will get very little out of class. That will show up in your grade.
Ask questions in class. If you do not understand something, ask a question about it.
Ask questions outside of class. Either come to office hours or use email.
For email, please use a subject indicating that you are asking a question for CSCI 4602, and always include your name in your email. Please send email to the address listed on the first page of this syllabus. Do not expect immediate answers. Give yourself time to get answers.
Do the homework. Homework does not count directly in your grade. If you do not do the homework, you will get no feedback on your work. If you get no feedback on your work, you will do poorly on the exams. If you do poorly on exams, you will get a poor grade in this course. If you get a poor grade in this course, you might not graduate. Do the math.
Do not copy homework answers from the internet. Getting feedback on someone else's work will not help you at all.
Schedule time to work outside of class.
Read relevant sections of the book twice. Take a break (a whole day or longer) in between. Later in the term, go back over your notes and book sections that you looked at earlier in the term. You will learn much more that way.
Get adequate sleep. Sleep is important both before and after you learn new concepts. Sleep before enables you to concentrate and think clearly, and sleep afterwards is critical for moving new information into permanent memory.
For information about
please see the auxiliary information at http://www.cs.ecu.edu/~karl/4602/fall16/syllabus-aux.html.