Stephen Fenner
Telephone: 803-777-2596 (only if I'm there; email is preferred)
Email: fenner IN THE DOMAIN cse.sc.edu
Web: http://www.cse.sc.edu/~fenner
Office: Swearingen 3A65, or via email
Office Hours: MW 3:00 - 4:45
Required: M. Sipser, Introduction to the Theory of Computation (Second Edition). Thomson, 2006.
The official departmental syllabus for this course can be found here.
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, as well as having close connections with logic and the foundations of mathematics.
CSCE 350 or MATH 526 or MATH 544 or MATH 574
| Homework assignments | 0% |
| Two midterm exams | 25% each |
| Final exam | 50% |
PLEASE NOTE:
The homework is largely intended as practice for the exams and as timely feedback for you. Homeworks will be "lightly" graded and returned with comments. Doing well on the homework does not require getting all answers right. More importantly, you will do well on the homework provided you hand it in regularly and make an honest effort to solve the problems.
Letter grades correspond to score percentages as follows:
| A | 90 or above |
| B+ | at least 87 and less than 90 |
| B | at least 80 and less than 87 |
| C+ | at least 77 and less than 80 |
| C | at least 70 and less than 77 |
| D+ | at least 67 and less than 70 |
| D | at least 60 and less than 67 |
| F | less than 60 |
You (the student) are expected to read all assigned material before the lecture begins. If for some reason you cannot attend class, you are responsible for any material covered during your absence.
Undergraduate and graduate students will be graded with different criteria. Graduate students will be given extra problems on the homework, and full graduate credit on an exam requires a higher score than full undegraduate credit. More specifically, on a 100-point exam, for example, the percent scores for graduates will be their raw scores. The percent scores for undergraduates will be their raw scores multiplied by 100/85. So a score of 85 points on the exam constitutes full undergraduate credit. If an undergrad scores over 85, the excess amount will count as extra credit towards her or his final grade.
There will be a strict late policy. Written homework will be due at a set time (the beginning of lecture, say) on the due date, unless otherwise specified. This is a sharp deadline.
Tests are given in class or via APOGEE and are open-book/open-notes. You may use any printed materials you wish during the test, but you may not use electronic devices of any kind, except for legitimate use by special needs students with prior notice. No make-up exams will be given except under extreme circumstances with a valid excuse, in which case you must give me notice well before the exam if at all possible.
You are expected to know the Academic Code of Responsibility as it appears in the Carolina Community: Student Policy Manual.
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 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.
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 appropriate University entities. 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.
Course topics by chapter and exam dates are given below. Any topics in brackets "[ ]" do not correspond to current sections in the book. Except for the dates and times of the midterms and the exams, 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. You will be tested only on those topics that could be covered in class, which means that the content of the exams may be adjusted. We will not cover Chapters 2 or 6. The midterm and final exam dates are set and inflexible.
| Topic(s) | Chapter | Week(s) |
| Introduction: mathematical preliminaries, definitions, theorems, proofs | 0 | 1 |
| Regular languages: automata, nondeterminism, regular expressions, nonregular languages, [possibly the Myhill-Nerode theorem] | 1 | 2 - 4 |
| The Church-Turing thesis: Turing machines and their variants,
algorithms Midterm Exam I: in class Wednesday, February 13, on Chapters 0-1 |
3 | 4 - 6 |
| Decidability: decidable languages, the halting problem | 4 | 6 - 8 |
| Reducibility | 5 | 9 - 10 |
| [Rice's Theorem] Intro to complexity Midterm Exam II: in class Wednesday, April 2, on Chapters 3-5 |
7 | 11 |
| Time complexity: P, NP, NP-completeness, polynomial time reducibility, Cook-Levin theorem | 7 | 11 - 13 |
| Space Complexity: Savitch's Theorem, PSPACE, PSPACE-completeness, L and NL | 8 | 13 - 14 |
| Review | 9 | 15 |
| Final Exam: Wednesday, April 30, 5:30 - 8:30 pm, location TBA -- Cummulative, but emphasizing Chapters 7-8 | 4 |
Last updated Monday January 28, 2008 at 16:50:19 EST.