| Class meeting | 11:00-11:50 MWF Howell North 106 | |||
|---|---|---|---|---|
| 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/fall18/ | |||
| My web page | www.cs.ecu.edu/~karl/ | |||
| Text: | Introduction to the Theory of Computation (third edition) by Michael Sipser |
The prerequisite for this course is CSCI 2405 and 2530 or equivalent. You should have enough of a knowledge of computer programming to understand how simple programs are written. 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, 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.
After successful completion of this course, you should be able to do the following.
Analyze a given DFA and/or NFA and determine the language recognized by it.
Design a DFA and/or NFA 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 exams 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 will take place on Monday, December 10, from 11:00 to 1:30 in regular classroom. You can bring two prepared 8.5x11" pieces of paper to the final exam.
Grades will be computed as follows.
| Grading | |
|---|---|
| Homework | 10–25% |
| 4 midterm exams | 40–60% |
| A comprehensive final exam | 20–35% |
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% |
| A– | 90% |
| B+ | 87% |
| B | 83% |
| B– | 80% |
| C+ | 77% |
| C | 73% |
| C– | 70% |
| D+ | 67% |
| D | 63% |
| D– | 60% |
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.
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.
This schedule has been revised to account for days lost to Hurricane Florence.
The following schedule lists brief topics along with sections from the book that cover them. All reading assignments are from the textbook.
Exam dates list review material for the exam.
This outline is tentative and might need to be adjusted, based on how many questions there are, how quickly we are able to cover topics and whether there are weather emergencies that force the university to close.
Some of the topics are short and will allow prior or subsequent topics to be addressed on the same day. Some topics might need to be skipped if time does not allow covering them.
| Date | Topics | Reading |
|---|---|---|
| M. 8/20 |
Syllabus. Sets, set notation, operations on sets, sets of sets. Alphabets and strings. Languages. Correspondence between strings and nonnegative integers. |
0.1 0.2 Sets Strings and languages. |
| W. 8/22 |
Sets as computational problems. Algorithms that compute sets. Examples of algorithms that compute sets. Functions. Functions as computational problems. Algorithms that compute functions. Examples of algorithms that compute functions. |
0.2 functions 0.3 0.4 |
| F. 8/24 |
Classes of problems induced by models of computation. Separating problems from algorithms. Deterministic finite-state machine (DFA) diagrams. "Running" a DFA. |
1.1 finite automata examples of finite automata designing finite automata |
| M. 8/27 |
Assignment 1 assigned Examples of DFAs. States correspond to sets of strings. Definition of a DFA. Definition of the set accepted by a DFA. |
1.1 designing finite automata formal definition of a finite automaton formal definition of computation |
| W. 8/29 |
The class of finite-state languages. Proving that a language is not finite-state. |
1.4 first few paragraphs We will use a method that is much simpler than the pumping lemma, but is just as rigorous. |
| F. 8/31 | Examples of proofs that a language is not finite state. | |
| M. 9/3 | Holiday | |
| W. 9/5 |
Assignment 1 due. Go over assignment 1. Nondeterministic finite-state machines (NFAs). Definition of an NFA. Definition of the set accepted by an NFA. |
1.2 nondeterminism formal definition of a NFA |
| F. 9/7 |
Equivalence of computational power of DFAs and NFAs. The subset construction. |
1.2 nondeterminism formal definition of a NFA equivalence of NFAs and DFAs |
| M. 9/10 |
Assignment 2 assigned. Closure results for finite-state languages. Regular operations. Regular expressions. |
1.1 the regular operations 1.2 closure under the regular operations 1.3 regular expressions |
| Tu. 9/11 – Tu. 9/16 | ECU closed due to hurricane. | |
| W. 9/19 |
Regular languages. Proof that all finite-state languages are regular. |
1.3 equivalence with finite automata |
| F. 9/21 |
Assignment 2 due. Go over assignment 2. General models of computation. Turing machines. Turing machines that compute sets. Turing machines that compute functions. |
3.1 Turing machines (TMs) examples of TMs |
| M. 9/24 |
Turing machines as strings. Interpreters. Turing-decidable (computable) sets. Examples of Turing-decidable sets. |
3.1 formal definition of a TM |
| W. 9/26 |
Turing-recognizable (partially computable) sets.
Enumerators. Equivalance of enumerability and partial computability. |
3.2 enumerators variants of TMs, multi-tape TMs |
| F. 9/28 | Exam 1 |
Preliminaries. DFAs. Definition of DFAs. Proof that a language is not finite-state. |
| M. 10/1 |
Assignment 3 assigned. The Church/Turing thesis. Computable questions about DFAs. |
3.3 the definition of an algorithm the Church/Turing thesis Terminology for describing Turing machines 4.1 decidable problems concerning regular languages |
| W. 10/3 |
Problems about TMs. Apparent difficulty of problems about TMs. |
3.3 Hilbert's problems 4.2 undecidability |
| F. 10/5 |
The Halting Problem. Diagonalization. |
4.2 the diagonalization method undecidability an undecidable language 5.1 halting problem |
| M. 10/8 | Fall break | |
| W. 10/10 |
Assignment 3 due. Go over assignment 3. More diagonalization. |
|
| F. 10/12 |
M-reductions between sets. M-reducibility. Properties of m-reducibility. Using m-reducibility to prove undecidablility. |
5.3 mapping reducibility |
| M. 10/15 | Proofs of uncomputability using m-reducibility. |
5.1 Theorems 5.2–5.4 |
| W. 10/17 | Exam 2 |
The Church/Turing Thesis. Computability. Enumerators. Problems about Turing machines. |
| F. 10/19 |
Assignment 4 assigned. Rice's theorem. |
Rices theorem |
| M. 10/22 |
M-complete problems. The halting problem is m-complete. Every m-complete set is uncomputable. |
|
| W. 10/24 |
Polynomial time. Class P. Examples of problems in P. |
7.1 measuring complexity big-O and small-o notation 7.2 |
| F. 10/26 |
Assignment 4 due. Go over assignment 4. Non-polynomial-time algorithms. Separating problems from algorithms. |
|
| M. 10/29 |
Nondeterministic polynomial-time algorithms. Class NP. Examples of problems in NP. |
7.3 the class NP examples of problems in NP |
| W. 10/31 |
Polynomial-time m-reductions. Properties of polynomial-time m-reducibility. NP-completeness. |
7.4 NP-completeness polynomial time reducibility |
| F. 11/2 |
Assignment 5 assigned
The Satisfiability Problem for propositional logic. The Cook/Levin Theorem. |
7.4 the Cook-Levin theorem |
| M. 11/5 | Exam 3 | Diagonalization. M-reductions and m-reducibility. Properties of m-reducibility. Proof of uncomputability using m-reducibility. Rice's theorem. |
| W. 11/7 |
The P = NP question. Using reductions to show NP-completeness. An NP-complete problem. |
7.3 the P versus NP question 7.4 Theorem 7.32 Corollary 7.42 |
| F. 11/9 |
Assignment 5 due. Go over assignment 5. More NP-complete problems. |
7.5 the Vertex Cover problem the Subset Sum problem |
| M. 11/12 | More NP-complete problems. |
7.5 the Hamilton Path problem |
| W. 11/14 | Elementary reductions: special cases. | |
| F. 11/16 |
Assignment 6 assigned. coNP and coNP-complete problems. NP ∩ coNP. Turing reductions and NP-hard problems. |
7.3 paragraph just above "the P vs NP question" |
| M. 11/19 |
Practical consequences of NP-completeness. Approximation algorithms. |
10.1 approximation algorithms |
| W. 11/21 to F. 11/23 | Thanksgiving break. | |
| M. 11/26 |
Assignment 6 due. Go over assignment 6. |
|
| W. 11/28 | Exam 4 |
Deterministic and nondeterministic polynomial-time algorithms. P and NP. The P = NP question. Polynomial-time m-reductions. NP-completeness. Proof of NP-completeness. coNP and coNP-complete problems. |
| F. 11/30 | Probilistic algorithms |
10.2 probabilistic algorithms |
| M. 12/3 | Review. | |
| Tu. 12/4 | Reading day. | |
| M. 12/10 | Final exam, 11:00am–1:30pm. |
For information about
please see the auxiliary information at http://www.cs.ecu.edu/~karl/4602/fall16/syllabus-aux.html.