| Time: | MW 11:00am - 12:15pm |
| Place: | Swearingen 2A11 (Section 001) or remotely via APOGEE (Section J60) |
| Instructor: | Stephen Fenner |
| Office Hours: | MW 1:00pm - 2:00pm, Storey Innovation Center, Room 2249 |
| E-mail: | FENNER in the cse dot sc dot edu domain |
| TA: | Canyu Zhang (canyu at email dot sc dot edu) |
| TA's Office Hours: | MW 10:00am - 12:00pm, Innov. room 2242 |
| Course Homepage: | https://cse.sc.edu/~fenner/csce551/index.html |
| Required Text: | M. Sipser, Introduction to the Theory of Computation (Third Edition). CENGAGE, 2013 (You can get by with the 2nd edition, and it may be a lot cheaper.) We will focus on the material in Chapters 1, 3-5, and 7, 8. |
CSCE 350 or MATH 526 or MATH 544 or MATH 574 or the equivalent
Includes course goals and topics covered.
This course is a mathematical introduction to the basic concepts underlying all computation. The goal is to discover the fundamental abilities and limitations of computers. We will study abstract models of computation, such as finite automata and Turing machines. We will also set up a formal framework for defining computational problems, with the goal of classifying problems according to their difficulty (aka, their complexity, that is, the amount of computational resources needed to solve them). We will see that some problems cannot be solved by computers at all, even given unlimited resources, and that other problems can be solved, but not efficiently. The three primary areas that we will cover are automata, computability, and computational complexity. The core topics learned in this course pop up repeatedly in many areas of computer science and other disciplines, as well as having close connections with logic and the foundations of mathematics.
The course conduct and rules given below may be subject to change on short notice during the semester, at my sole discretion. In particular, the course modality may switch to all virtual.
Regular written homework will be assigned but not graded. It is intended to prepare you for the quizzes and the final exam.
Students taking the course for graduate credit or Honors College credit will be required to hand in some additional homework exercises. This homework will be assigned in the latter part of the course. Performance on the additional homework exercises will be worth the equivalent of one letter grade.
There will be six quizzes, 30 minutes each, taken in class during the first half hour, and a final exam, lasting 2.5 hours. Quiz 1 is during the 7th class period, and subsequent quizzes occur in every 4th class period thereafter, except for Quiz 6, which occurs three class periods after Quiz 5. They are all on Wednesdays except Quiz 6, which is on a Monday. Each quiz will include two or three questions, depending on difficulty. Quiz questions will be related to the previous homework exercises and problems.
Here is the schedule of quizzes and the final exam.
| Exams | Date | Class Period |
| Quiz 1 | Wed Jan 31 | 7 |
| Quiz 2 | Wed Feb 14 | 11 |
| Quiz 3 | Wed Feb 28 | 15 |
| Quiz 4 | Wed Mar 20 | 19 |
| Quiz 5 | Wed Apr 3 | 23 |
| Quiz 6 | MON Apr 15 | 26 |
| Final | Sat Apr 27, 4:00pm - 6:30pm |
Exams and quizzes are all open book/open notes. You may use any hand-written or printed materials you wish during the test, but you are NOT allowed electronic devices of any kind, except for legitimate use by special needs students registered through the university's Office of Student Disability Services and with prior notice, or for remote test proctoring. No make-up exams will be given except under extreme, emergency circumstances with a valid excuse, in which case you must give me notice well before the exam if at all possible.
Each quiz is worth 10% of your grade. The final exam is worth the remaining 40%. The mapping of overall percentages to letter grades is as follows:
| A | 90 or above |
| B+ | at least 86 and less than 90 |
| B | at least 80 and less than 86 |
| C+ | at least 76 and less than 80 |
| C | at least 70 and less than 76 |
| D+ | at least 66 and less than 70 |
| D | at least 60 and less than 66 |
| F | less than 60 |
PLEASE NOTE:
You are expected to know the Academic Code of Responsibility as it appears in the Carolina Community: Student Policy Manual. You are also expected to know the class policies outlined below.
You may not represent other people's work as your own. For this CSCE 551 class specifically, this means that you cannot submit specific answers from other sources without proper attribution. If you copy or otherwise derive materials/answers from other people, books, the web, etc., you must cite your source(s) in a way that adheres to the usual standards for an academic paper. Deriving/copying without proper attribution is plagiarism, which I regard as a serious offense. (Exceptions: You do not need to explicitly cite any material you lift from the Sipser text or from my own lectures. You are also not required to explicitly cite any general background material you use for an answer but that does not specifically relate to the actual question being answered.)
Obtaining answers during an exam other than by the approved means (your own written or printed material and cleverness) is forbidden. Passing along questions or answers to an exam to anyone else before the exam is given is also forbidden.
I am also applying the following from the Office of Student Conduct
and Academic Integrity:
"Lectures and course materials (which is inclusive of my presentations,
tests, exams, outlines, and lecture notes) may be protected by
copyright. You are encouraged to take notes and utilize course
materials for your own educational purpose. However, you are not to
reproduce or distribute this content without my expressed written
permission. This includes sharing course materials to online social
study sites like CourseHero, Chegg, and other services. Students who publicly
reproduce, distribute or modify course content may be in violation of
the university's Honor Code's Complicity policy, which states: sharing
academic work with another student (either in person or
electronically) without the permission of the instructor is in
violation of the honor code. To best understand the parameters around copyright and intellectual property review ACAF 1.33 'Intellectual Property Policy'."
Any violation of the rules above constitutes cheating, for which there is no excuse.
THE USUAL PENALTY FOR CHEATING IS FAILURE OF THE COURSE. The offense will also be reported to the University's Academic Integrity office, which will handle any further sanctions. The bare minimum penalty you may receive for an instance of cheating is double the points of the assignment off. That means that if an assignment/test is worth 10 points, your ultimate grade would be -20 for the assignment/test. Finally, as noted in the Student Policy Manual, the maximum penalty for cheating on an assignment is expulsion from the University. These penalties apply both to copier and copiee.
If you have any questions or doubts about this policy, you should ask me.
Course topics by chapter are given below. Any topics in brackets "[ ]" do not correspond to current sections in the book. This schedule is flexible and is subject to some revision as the class proceeds. There may not be time to cover all the topics listed. We will not cover Chapters 2, 6, or 10, but some Chapter 6 material may be relevant to the graduate exercises.
| Topic(s) | Chapter | Approx. No. of Weeks |
| Introduction: mathematical preliminaries, definitions, theorems, proofs | 0 | 1 |
| Regular languages: automata, nondeterminism, regular expressions, nonregular languages, [possibly the Myhill-Nerode theorem] | 1 | 3 |
| The Church-Turing thesis: Turing machines and their variants, algorithms | 3 | 2 |
| Decidability: decidable languages, the halting problem | 4 | 2 |
| Reducibility [possibly Rice's Theorem] | 5 | 2 |
| Intro to complexity |
7 | 1 |
| Time complexity: P, NP, NP-completeness, polynomial time reducibility, Cook-Levin theorem | 7 | 3 |
| Space-bounded computation | 8 | 1 |
| Final Exam (see above for date and time) |
Last updated Monday January 8, 2024 at 13:53:39 EST.