University of Minnesota
CSCI4011: Automata, Computability & Complexity
CSci 4011, Fall 2021


Carl Sturtivant,


Sipser, “Introduction to the Theory of Computation”, 3rd Edition, Cengage, 2013

be sure NOT to get the ‘international edition’ as it has different exercises and problems.

Other books of interest

  • Harel, “Algorithmics”, Addison Wesley,

    –- for a broad overview of the abstract concepts of computer science with little mathematics.

  • Garey and Johnson, “Computers and Intractability, a Guide to the Theory of NP-Completeness”, Freeman & Company

    –- an excellent reference to NP-completeness and its practical ramifications.

COVID-19 Link

Here's what is expected of you, and is a part of this syllabus.

Read this document very carefully, as it defines what is required to perform effectively in this class. You will be assumed to have read and understood this syllabus: ignorance is not an excuse. If later in the semester you realize for example, that you can't attend the final exam, this will be your fault and no makeup exam will be supplied. Avoid attempting to make yourself an exception.

Course content very approximately in temporal order is as follows. However some subjects may be approached non-linearly because of natural cross connections in the material.

Mathematics from chapter zero of the text will be assumed as needed (via the prerequisite).

Sections of the book listed below should be read in conjunction with the class. As the class proceeds it should be clear which sections have just been covered in order, and therefore which are about to be covered. The course content is defined by the sections listed below.

Chapter 1

Finite automata and regular languages.

Chapter 2

Context-free languages, grammars. Excludes §2.2, §2.4.

Chapter 3

Turing machines and the formal definition of an algorithm.

Chapter 4

Decidability, and the Halting Problem.

Chapter 5

Reductions and provably unsolvable problems.

Chapter 6

The Recursion Theorem, Decidability of Logical Theories. Excludes §6.3, §6.4.

Chapter 7

Time complexity and NP-completeness.


The following will only be surveyed with some proofs.

Chapter 8

Space complexity.


Circuit complexity.


Parallel computation.



Evaluation: The following rules will be strictly enforced.

Evaluation will consist of assignments (7), a Midterm exam, and a Final exam. Assignments are a vital part of the learning process: persons who do not submit reasonable attempts at all seven assignments will receive an F for the course. Examinations are open book and open notes.

Due dates for all assignments are strict: all homeworks must be received by gradescope before or during the day they are due in order to receive credit.

Grading is absolute (i.e. not on a curve). The overall grade will be based upon: 8% for each homework, 6% for the midterm, and 30% for the final. In addition 8% of the course will be recorded for scholastic conduct. Students who do not violate the scholastic conduct rules (see below) will receive the full 8%. A minimum of 60% is necessary for an S or C- grade.

Grading will be as follows: 95.0% or above yields an A, 90.0% an A-, 85% = B+, 80% = B, 75% = B-, 70% = C+, 65% = C, 60% = C-, 55% = D+, 50% = D, and less than 50% yields an F. Percentages are not rounded when using this scheme, because this would be tantamount to moving all of the grade boundaries down by 0.5%.

If you have a question about grading, address it to the TAs via Gradescope by making a regrade request. Only if something wholely unreasonable has occurred will the instructor intervene.

Furthermore, there is a limit of 10 days from when an assignment's grade is posted online for grading problems to be dealt with. So check your grades online frequently.

Incompletes will in general not be given. An incomplete will be considered only when a provably serious family or personal emergency arises during the end part of the course, proof is presented, and the student has already completed all but a small portion of the work.

Make-up Exams will in general not be given. Verify at the start of the semester that you can attend all exams at the stated dates and times, and if you cannot do so, then withdraw from the course. A make up exam will be considered only when a provably serious family or personal emergency arises during the relevant part of the course, and proof is presented.

Scholastic conduct must be acceptable. Specifically, you must do your homeworks, and examinations yourself, on your own. Read these linked documents as a part of this syllabus.

Do not search for homework related information on the World Wide Web; we do this and will recognize any logical idiosyncrasies from such answers that occur in your homework. Plagiarism in the widest sense is forbidden. Generate your own solutions.

In the event of academic misconduct on your part the Office for Community Standards will be consulted to see if there's a record of a prior instance of academic misconduct. OSC will be notified of the present misconduct, so that future misconduct can be appropriately penalized.

Also the instructor will decide privately if the misconduct in the present class is egregious or not. Included in the egregious category of misconduct is any sort of plagiarism where the student does not understand completely the material plagiarized. However, any academic misconduct is open to being decided to be egregious by the instructor.

If there was a prior instance of academic misconduct or if the present misconduct is egregious, the penalty given for academic misconduct by the instructor is an F for the entire course. Note that OSC may independently decide in some cases to award an additional penalty, such as suspension or even expulsion from the University.

Only in the case that there is no prior instance of academic misconduct and the instructor decides that the academic misconduct is not egregious will a lesser penalty be possible. OSC will still be notified.

The instructor may at their discretion at any time give any student a short oral quiz on a student's submitted answer to any homework question to determine whether the student understands the text they have supplied. Failure to supply an adequate response will be deemed evidence for academic dishonesty (plagiarism), which may lead to failing the course and disciplinary action from the university.