Syllabus for CSCE 551
Theory of Computation
Spring 2024

Prerequisites

CSCE 350 or MATH 526 or MATH 544 or MATH 574 or the equivalent

Bulletin Description

Includes course goals and topics covered.

Overview

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.

Overview of topics

1. Finite Automata and Regular Languages
   • deterministic vs dondeterministic automata
   • regular expressions
   • closure properties of regular languages
   • nonregular languages
   • minimization and the Myhill-Nerode theorem
2. Turing Machines and Computability Theory
   • the Church-Turing thesis
   • decidable and undecidable problems
   • reductions between problems
3. Computational Complexity Theory
   • P, NP, and PSPACE
   • polynomially bounded reducibility
   • The Cook-Levin theorem
   • NP-completeness
   • PSPACE-completeness

Important Note

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.

Homework

Regular written homework will be assigned but not graded. It is intended to prepare you for the quizzes and the final exam.

Graduate Requirements versus Undergraduate Requirements

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.

Exams

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.

Quizzes and exams forJ60 students

• Each quiz will be emailed to you at the start of class on the quiz day. You have 30 minutes to answer the quiz question(s) plus an additional 5 minutes to upload your answers to CSE Dropbox. You must have your answers uploaded before the Dropbox window closes 35 minutes after the start of class (i.e., before 11:35am) or you will get a 0. If Dropbox is unavailable because of a general network outage or the like, you should email your answers directly to the TA ([email protected]) and copy me ([email protected]) BEFORE the Dropbox deadline.
• You will take the final exam remotely using remote proctoring resources. See this site. More information on this later.

Here is the schedule of quizzes and the final exam.

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.

How Course Grades Will be Determined

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:

PLEASE NOTE:

1. This course will go by quickly. The subject matter requires time and effort to digest, and so it is vital that you keep up with the homework and reading.
2. The course is mathematical in nature. The second most important indicator of success in this course (second to diligent work) is a certain level of mathematical maturity, that is, being able to: (a) understand mathematical definitions and theorems, (b) verify proofs (detect flaws in false proofs), (c) solve mathematical problems, and (d) in simple cases, generate one's own definitions, theorems, and proofs.
3. There will be no required programming assignments, and prior programming experience is not a prerequisite for this course.

Code of Student Academic Responsibility

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.

Rough Schedule of Lectures

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.

Last updated Monday January 8, 2024 at 13:53:39 EST.