| Class meeting | Section 001: 12:00–12:50 MWF Austin 306 Section 002: 2:00–2:50 MWF Austin 306 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Canvas page | https://ecu.instructure.com/courses/90111 |
| Course web page | www.cs.ecu.edu/~karl/4602/fall22/index.html |
| My web page | www.cs.ecu.edu/~karl/index.html |
| Lecture notes: | Lecture Notes for CSCI 4602 Karl Abrahamson |
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.
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 describe 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 in the worst case.
Before asking what can be computed, we need an understanding of the nature of computation. We will study a simple model of computation and explore what can be computed with that simple model.
The following is an outline of this course.
Mathematical Preliminaries
Finite-state computation
Algorithms and computability
Polynomial-time computability and complexity
After successful completion of this course, you should be able to do the following.
Design a deterministic finite-state machine recognizing a specified language.
Analyze a given deterministic finite-state machine and determine the language that it recognizes.
Analyze or design a regular expression specifying a given language.
Prove that a given language in not regular.
Explain the significance of Church-Turing Thesis.
Define computability.
Describe properties of reductions.
Use reductions to prove uncomputability.
Use Rice's Theorem to prove uncomputability.
Describe a few uncomputable problems.
Define the complexity classes P, NP and Co-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 doing a 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.
You are expected to attend class. Students who do not attend class can expect to do poorly in this course. I will not take attendance.
If you do not attend class, you will be expected to get all information that was covered in class from another source.
Office hours will take place in my office. Office hours are as follows.
| MW 9:30–9:50am |
| MW 11:00–11:50am |
| MW 1:30–1:50pm |
| or by appointment |
Tutors are available. See https://cet.ecu.edu/csci/about-us/about-the-department-2/.
Grades will be computed as follows.
| Grading | |
|---|---|
| 3 50-minute quizzes | 55–75% |
| A comprehensive final exam | 25–45% |
Percentages will be chosen on an individual basis from the indicated range to give you your best score. All quizzes have the same weight.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| Grade cutoffs | |||||||
|---|---|---|---|---|---|---|---|
| A | 93% | B+ | 87% | C+ | 76% | D+ | 64% |
| A– | 90% | B | 83% | C | 72% | D | 60% |
| B– | 80% | C– | 68% | D– | 56% | ||
There will be a 50-minute quiz on each of the following dates.
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 it.
The final exam will take place on
You can bring two prepared 8.5x11" pieces of paper to the final exam.
There is a practice quiz for each quiz. Print and complete the practice quiz and bring the completed quiz to class on the due date. We will go over the practice quiz in class.
Note: You will learn more if try to answer questions before you see the answers, even if your answer is incorrect. You will do better if you work the practice quizzes before seeing the answers.
| Practice quiz | Due date |
|---|---|
| Practice quiz 1 | M. September 19 |
| Practice quiz 2 | M. October 24 |
| Practice quiz 3 | F. November 18 |
You will need to have a computer and internet connectivity to work the practice quizzes, which are on Canvas. In the event that the class is moved temporarily online, you will also need a computer and internet connectivity to access additional course material.
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. Use office hours or 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. If you have not received a reply for a few days, please resend your email.
Do the practice quizzes. That will help you to do well on the real quizzes.
Schedule time to work outside of class.
Repetition is the key to learning. Read relevant sections of the lecture notes twice. Take a break (a whole day or longer) in between. Later in the term, go back over your notes and the lecture 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.
East Carolina University seeks to comply fully with the Americans with Disabilities Act (ADA). Reasonable accommodations will be made for students with verifiable disabilities. In order to take advantage of available accommodations, students must be registered with the Department for Disability Support Services located in Slay 138, 252-737-1016. See Accommodation Information & Processes.
Additional DSS student resources can be found at: https://accessibility.ecu.edu/students/.
In the event of a weather emergency, information about ECU can be obtained through the following sources:
| ECU emergency notices | http://www.ecu.edu/alert |
|---|---|
| ECU emergency information hotline | 252-328-0062 |
Smoking is not permitted in classrooms.
Students are expected to abide by the university's Student Honor Code.