| Class meeting | Section 1: 1:00–2:30 MWF Bate 1031 Section 2: 3:00–4:30 MWF Bate 1031 |
|---|---|
| Instructor | Karl Abrahamson |
| abrahamsonk@ecu.edu | |
| Canvas page | https://ecu.instructure.com/courses/52350 |
| Course web page | www.cs.ecu.edu/~karl/4602/fall20/index.html |
| My web page | www.cs.ecu.edu/~karl/ |
| 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. 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.
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.
Analyze a given deterministic finite-state machine and determine the language that it recognizes.
Design a deterministic finite-state machine recognizing a specified language.
Analyze or 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.
Define computability.
Describe properties of reductions.
Use reductions 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 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.
If face-to-face instruction should no longer be possible, this course will switch to an online course. That switch might be mandated at any time. In that case:
All students are required to comply with the University Regulation on Face Coverings, including the wearing of face coverings in classrooms, lecture halls, and any other instructional areas and campus locations. Students with disabilities and medical conditions, as documented with the Department for Disability Support Services, may seek alternate accommodations. For additional information please consult the Office of Students Rights and Responsibilities Website.
ECU wants to provide the safest classroom environment possible this semester. Therefore, we will be observing the following class policies related to your health and safety per Pirate Nation Guidelines:
All students are required to comply with the University Regulation on Face Coverings. No student will be allowed into the classroom without a face covering or mask worn properly over both the mouth and nose. You must wear a face covering properly the entire time you are in class.
If you do not have access to a face covering, you may obtain a mask from Dowdy Student Store, Pirate Pantry, or another provider of masks.
Maintain appropriate social distancing in hallways or common spaces prior to or after class.
Follow all posted signage related to entry, exit and pedestrian flow within classroom buildings.
Clean your desk surface with disinfectant when you arrive and before you leave class.
Be prepared to sanitize high-touch surfaces, such as chairs, desks. For additional information please consult ECU's Cleaning and Disinfecting Hand-out.
Maintain a minimum of 6 feet between you, other students and the instructor when entering, leaving and during class.
Sit in your assigned seat.
Conduct a daily health screening using the CDC's COVID-19 symptoms list.
Do NOT attend class if you answer yes to any item on the list or if you are experiencing symptoms of any illness. Contact me as soon as you can if you need to stay away from class because of illness.
This course is currently planned to use face-to-face instruction. Quizzes and the final exam will take place in the classroom. Scans of graded quizzes will be returned to you by email.
You will need to read the notes for each class day.
Quizzes will be made available online at 1:00 for section 1 and at 3:00 for section 2. You will have 60 minutes to complete them.
Quizzes must be completed as Microsoft Word documents. You can include graphics if you choose to. Completed quizzes must be submitted using submit as described under practice questions. The assignment name for quiz 3 is quiz3. Generalize that to other quizzes.
The final exam will be made available 1/2 hour before the beginning of the final exam time, according to the university calendar, and will be due by 1/2 hour after the exam period ends. Follow the rules for quizzes. The assignment name for the final exam is final.
Attendance is required. You will need to subscribe to Top Hat. You will receive an email about it from Top Hat. At each class period I will write a number on the board that you can use to register your attendance.
The instructor will take attendance and utilize a seating chart in order to facilitate contact tracing, should this become necessary.
Students should make every effort to participate in class activities, such as exams or key assignment due dates.
Missing class does not automatically result in extensions on assignments or exam due dates.
There is a clear correlation between attendance/participation and your grades.
It is the student's responsibility to seek out the instructor and other classmates to obtain the information (e.g., lecture notes, relevant announcements, etc.) if they missed class.
Students should maintain regular communication with instructors regarding their health status and communicate any changes in their ability to complete coursework and academic responsibilities immediately.
If you become ill, see the guidelines in Return of Pirate Nations for Students. No unnecessary visits to health facilities or documentation will be required as per ACHA 2020.
You may at any time consult with your advisor or the instructor about whether to request an incomplete (ECU Faculty Manual IV.VIII.E Grade of Incomplete) or a Withdrawal (ECU's Withdrawals Policies). You will not be granted an incomplete simply because you did not attend class or exams without a university-recognized excuse.
You will need to be able to receive email from me. For some students, such email is put into a spam folder. (It will come from an actual email address that is different from the "from" or "return address" fields of the email. The actual sender is not an email server. That can cause spam filters to classify it as spam.) If you put my email address into your address book, it should cause the spam filter to let it go through.
There will be a 30 minute quiz on each of the following dates at the end of the lecture.
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.
Each of the Friday quizzes is on material represented by the practice questions that were assigned on or before the preceding Friday and due on or before the preceding Monday. You will get feedback by Wednesday before the quiz.
I will email you your graded quiz as a scanned document.
The final exam dates and times are as follows.
| Section 1: | Monday, September 28, 1:00–2:30, Bate 1031 |
| Section 2: | Monday, September 28, 3:00–4:30, Bate 1031 |
You can bring two prepared 8.5x11" pieces of paper to the final exam.
There is a practice question set for every lecture, due at 11:59 on the date of the next lecture. The practice questions to not count directly toward your grade, but I will return
Even though the practice questions do not count directly toward your grade, they do count indirectly. If you do the practice questions and get feedback on your answers, you will probably do well on the quizzes and final exam. If you do not do the practice questions and submit them, you will probably do poorly on the quizzes and the final exam.
Submit your answers to practice questions in a Microsoft Word document. You can include graphics in the document, but please be sure that I can write feedback to each question. Don't pack graphics together. Don't use formatting that makes it difficult for me to edit your work.
Each assignment has a name. An assignment that is due on 8/14 has name 0814. Generalize that to other dates. All assignments names are 4 digits long.
As soon as possible, be sure that you are able to log into xlogin.cs.ecu.edu using NoMachine or other ssh-compatible client. Also 6 be sure that you are able to transfer a file to xlogin. (You can use a tool such as WinSCP or you can attach a file to an email message and open email using Firefox (via mymail.ecu.edu). Be sure that you are able to use the submit utility on xlogin.
To submit assignment assn, do the following.
Log into xlogin.cs.ecu.edu.
Transfer the file that you want to submit.
With you current directory set to the directory that contains the file that you want to submit, run command
~abrahamsonk/4602/bin/submit assn file
where assn is the name of the assignment
and file is the name of the document
that you are submitting. For example, to submit file 0814.docx
that is due on 8/14, use command
~abrahamsonk/4602/bin/submit 0814 0814.docxIf you have trouble with the Word files, all of the following are available as pdf files. Just replace docx by pdf.
Grades will be computed as follows.
| Grading | |
|---|---|
| Attendance | 10% |
| 6 quizzes | 50–70% |
| A comprehensive final exam | 20–40% |
Percentages will be chosen on an individual basis from the indicated range to give you your best score. All quizzes have the same weight.
You will lose 2% for each unexcused absence up to a maximum of 10%.
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% | ||
Office hours will take place remotely at the following times.
| Tu 10:00–11:30am, 2:00–3:00pm |
| Th 10:00–11:00am, 2:00–3:30pm |
| or by appointment |
To attend office hours during the listed times, log into https://ecu.webex.com/meet/abrahamsonk using Cisco Webex Meetings. You might be allowed to join the meeting automatically, or you might need to wait for me to admit you. If you have trouble, please send me an email.
You can find whiteboard controls at the left-hand side of the screen. To type text, click on Tt, then click on a position on the whiteboard and type. To draw, click on the pencil tool and draw using a mouse. You might need to select a color using the lower square in the tool bar. You might need to change from the pen tool to the pencil tool by clicking on the tool and selecting pencil.
Anyone can join at any time. If you join while someone else is talking to me, please remain quiet until the previous student is done. If you need to discuss something private, please set up a meeting with me by email.
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.
Do the practice questions and submit your answers, even though they do not count directly in your grade. If you do not submit answers to the practice questions, you will get no feedback on your work. If you get no feedback on your work, you will do poorly on the quizzes and final exam. 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.
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/.
Making up missed instructional time in this course will follow ECU's Policy for Making Up Missed Instructional Time Due to Suspension of Instruction.
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 |