Syllabus
CSCI 4602
Theory of Automata and Linguistics
Section 001
Fall 2016

Contents

---

1. Prerequisites
2. Course objectives
3. Student competencies
4. Attendance policy
5. Grading
6. Recommendations for success
7. Lecture schedule and reading assignments
8. Additional information

Prerequisites

---

The prerequisite for this course is CSCI 2427 or 2400 or equivalent knowledge of discrete mathematics. 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.

Course objectives

---

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 not based on computation.

Student competencies

---

After successful completion of this course, you should be able to do the following.

1. Demonstrate an understanding of how to describe and work with sets of strings and descriptions of computational problems.
2. Create a finite-state machine for a given computational problem.
3. Prove that a given computational problem cannot be solved by a finite state machine.
4. Write a regular expression that describes a given set of strings.
5. Define a given language using a context-free grammar.
6. Produce a parse tree for a given string according to a given context-free language.
7. Define computability.
8. Explain the Church/Turing thesis.
9. Recognize some uncomputable problems.
10. Perform elementary reductions between given problems, and prove that a given problem is not computable by performing a reduction.
11. Define P and NP.
12. Demonstrate that a given problem is in P.
13. Demonstrate that a given problem is in NP.
14. Prove that a given problem is NP-complete.
15. Explain the practical consequences of a problem being NP-complete.
16. Perform an elementary closure proof for a given class of languages.

Attendance policy and incompletes

---

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 are nearly done already, and have done work of acceptable quality that it is realistic that you can pass the course.

Grading

---

There will be a quizzes on each of the following dates.

1. Thursday, September 1
2. Thursday, September 15
3. Thursday, September 29
4. Thursday, October 13
5. Thursday, October 27
6. Thursday, November 10
7. Thursday, December 1

You can bring one prepared 8.5x11" piece of paper, written on both sides, to each quiz. You can write anything that you like on that paper. I will not collect them.

The lowest quiz score will be dropped, leaving 6 quizzes. There will be no makeups for missed quizzes. A missed quiz will be counted as a 0.

The final exam will take place on Tuesday, December 13, from 2:00 to 4:30 in Brewster D-309. You can bring two prepared 8.5x11" pieces of paper to the final exam.

Computing grades

Grades will be computed as follows.

Percentages will be chosen from the indicated range to give you your best score. All quizzes will have the same weight.

Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.

Recommendations for success

---

1. Attend class. Arrive on time.

2. 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.

3. Ask questions in class. If you do not understand something, ask a question about it.

4. 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.

5. Schedule time to work outside of class.

6. 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.

7. 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.

Lecture schedule and reading assignments

---

The following schedule lists brief topics along with sections from the book that cover them. All reading assignments are from Sipser.

Quiz dates list review material for the quiz.

This outline is tentative and might need to be adjusted, based on how many questions there are and on how quickly we are able to cover topics.

Additional information

---

For information about

• student conduct
• students with disabilities
• weather emergencies
• retention requirements

please see the auxiliary information at http://www.cs.ecu.edu/~karl/4602/fall16/syllabus-aux.html.