Course Syllabus

CSCI 4011: Inherent Limitations of Computer Programs

Spring 2026
4 Credits
Lecture: MW 1:00-2:15, Bruininks 230
Recitations:
    Section 2: F 12:20  -  1:10, Ford 150
    Section 3: F   1:25  -  2:15, Ford 150
    Section 4: F   2:30  -  3:20, Lind L120
    Section 5: F   3:35  -  4:25, Lind L120

Course Staff

Instructor:
Nick Hopper
hoppernj@umn.edu

TAs:
Listed on course staff page

Office Hours can be found on the course google calendar 

Course Overview

Did you ever have a hard time writing a program to do something, or making a program faster?  Maybe after trying for a long time you thought "this problem is impossible to solve."  Maybe you were right! This course is about using mathematical tools to formally prove that for some problems, no matter how smart you are,  you can't write a program to solve them, or you can't write a fast program to solve them.  In other words, we will be using mathematics to address the inherent limitations of computer programs.  The techniques we develop for doing so turn out to have many other interesting applications in computer science, such as compilers, string searching, program testing and verification, computer security, cryptography, and bioinformatics.

The course is divided into three units that approximately cover chapters 1-8 of the course textbook.

1. Languages and automata: In the first unit, we will develop a simple, mathematical model of a program, the finite automaton.  We will see some of the kinds of programs we can express as finite automata, develop a mathematical formalism for the kinds of problems we want to solve with programs, and prove that there are some simple problems that we can't program a finite automaton to solve.
   
   
2. Computability: In the second unit, we will develop a slightly more complex model of a program that turns out to exactly capture the kinds of programs we can write for any computer we know about, the Turing machine.  We will then prove that there are some problems that we can't write a program for, and develop ways to prove that a given problem can't be solved by a program.
   
   
3. Complexity Theory: Finally, we will introduce the notion of efficient programs, that run in a short time or use a small amount of memory.  We will introduce one of the most central questions in computer science, P versus NP, and develop methods to prove that a problem is unlikely to be solved by a fast program or one that uses a small amount of memory.  

Goals and Objectives

Students who complete this course should be able to:

• Convert between finite automata and regular expressions
• Construct regular expressions and context-free grammars for simple languages
• Program automata and Turing machines to solve simple recognition problems
• Apply the pumping lemma to prove that a language is not regular or context-free
• Prove via reduction that a given language is Undecidable
• Prove via reduction that a given language is NP-Hard
• Prove via reduction that a given language is PSPACE-Hard

A word about proofs. You may have noticed that the word "prove" plays a prominent role in this syllabus; you might guess this means proofs will play a prominent role in this course.  Many students in computer science believe they are "bad at proofs."   If you have done well in CSci 11X3 and 19X3 proofs should not scare you.

You may not have realized this before, but proofs are programs.  This is true in many senses: metaphorically, in that a proof is just a list of steps to convert an input (a set of assumptions) into an output, i.e., the conclusion; literally, in that many of the proofs in this class involve writing a program or algorithm that accomplishes some task; and in a very technical sense, a branch of logic known as constructive type theory actually establishes a one-to-one mapping between each program and the proof of some theorem. So if you learned to write good programs, you can learn to write proofs well. Ask yourself this: were you always good at writing programs?  Probably not.  How did you get better? By practicing, and seeing lots of examples of good programming.  In this class, you will practice writing proofs; the textbook and readings and solutions for the class will feature lots of examples of proofs.  The group work will involve practicing proofs, and homeworks will list extra problems that you can do for more practice.

More often than not, in the proofs for this class, the most important part of writing a proof will be understanding what you need to prove. In most proofs about computing, the definition of a property we want to prove lays out a set of steps we need to follow to prove the property. Thus you can expect that in this class, understanding the definitions given in class will play an important role in doing well on the graded work.

Prerequisites

The prerequisite for this course is CSci 2041, which has prerequisites of CSci 2011 and CSci 19X3. From CSci 2041 and 19X3 you will need to understand programming concepts like abstraction, iteration and recursion.  From CSci 2011 you will need to understand concepts like formal logic and propositions, sets, relations, functions, and graphs.  To make sure you remember the material from 2011, you should review Chapter 0 of the text.  If you have trouble with any of the exercises there, you probably need to do some extra work to get up to speed for this class.

Lecture Schedule

The course website includes a schedule of lectures for this course. The schedule includes the readings related to each class. Students are responsible for reading the appropriate materials for each lecture; we may not cover all of the reading material in the lecture but it may still appear on exams. Lecture slides will usually be linked from the homepage before class, but always within one day following the corresponding lecture.

Textbook

The required textbook for this course is Michael Sipser's "Introduction to the Theory of Computation", 3rd edition, ISBN 0534950973.  In addition to this text, we will provide a number of supplementary readings via Canvas.

Student Workload Statement

CSci 4011 is a 4 credit course.  Under the University Senate guidelines, each course credit should require an average student about 3 hours of work per week over a 14-15 week term to earn an average grade; so you should expect to do about 12×15 = 180 hours of work in this course.  A rough breakdown per week would be:

• 3.5 hours in class/discussion
• 30 minutes on self-check quizzes
• 2-3 hours on required readings
• 4-6 hours on homework.

Grading

Grading for the class will be based on five components:

• 12 Homeworks (10%): we will have weekly homeworks, to be submitted via Gradescope by 11:59pm each Wednesday.  Homeworks will consist of 3 problems, posted on the class website.  Questions that involve proofs should start with a short explanation of the proof idea, followed by a detailed proof, as in the course text.  Solutions to each homework problem should be on a separate sheet of paper to allow space for feedback. Remember to include your name on each page.  Homework problems will be graded on a 10-point scale as follows:
  
  

  Homework Problem Scoring

  Score	Explanation
  10 Points	The solution belongs in the textbook: it has no errors.
  8-9 Points	The solution has only minor errors: e.g. it is not clearly written or is missing a minor point.
  6-7 Points	The solution has the "right idea" but has one or more important gaps
  5 Points	The solution could possibly work but has a major error
  3-5 Points	The solution demonstrates understanding of the problem but is wrong or incomplete . (e.g. "I know that to prove this, I need to show (foo and bar) but I couldn't prove (bar) because (baz)...")
  1-2 Points	The solution does not demonstrate significant understanding of the problem; it is just plain wrong.
  0 Points	No solution was attempted

  
  Students should be aware that solving the homeworks is the minimal work involved to make sure you understand the course; if you have trouble with these problems, you should try more until you are sure you understand the material.
  
  Homework grading is performed by TAs. If you have a question about homework grades, you may address it directly to the grader via gradescope. Only if something wholly unreasonable has occurred will the instructor intervene.  Furthermore, there is a limit of seven days from the grading of an assignment for grading problems to be dealt with. After that period, no further grade revisions will be considered.
  
  Late Homeworks. You can submit a homework up to 24 hours after the due date for 75% credit, and up to 36 hours after the due date for 50% credit.  Homework solutions will be posted Fridays at noon, at which point homeworks that have not been submitted are worth 0 points.  
  
  Each student will be allowed two late homeworks (up to 36 hours) with no penalty.
• 25 Self-Checks (5%): Along with each lecture and assigned reading, there will be a short canvas "self-check" quiz worth 3 points, due by 11:59pm the day following the lecture.  Students will be allowed up to 3 attempts per quiz.
  
  
• Group Work (5%): In your discussion section, you will be assigned to a group.  Each week your group will be assigned several problems to solve, and then present the solutions to your TA in recitation.  Solutions will be graded on a 0-2 point scale. 

• 6 Quizzes (30%) We will have six quizzes, all during Friday discussion sections; the dates of these are already marked on the course schedule.  Each quiz will be graded on a scale from 0-10.  A student must score at least 60% on the total quiz grade to pass the course. 
  
  
• 2 Midterm exams (15% each): We will have two 75-minute midterm exams, the dates of which are already marked on the course schedule.  Midterms are not explicitly cumulative, but the materials in this course are arranged so that each new topic depends on the topics developed previously.
  
  
• Final exam (20%): The course will have a cumulative, 2-hour final exam.  67% of the material on this exam will be new, with the remaining 33% covering materials from the previous midterms.

If a student achieves a combined quiz score of at least 30/50, then composite scores will be assigned to grades as follows:

Score to grade table

Grade	Minimum Score
A	92.00
A-	90.00
B+	86.00
B	82.00
B-	80.00
C+	76.00
C	70.00
C-	66.00
D+	63.00
D	59.00
F	0

Graded Work Dropping Policy

Because life, in the form of officially excused absences or other reasons not officially recognized by the University may occasionally interfere in anyone's ability to complete assignments or attend discussions, we will allow every student to drop, for any reason (and with no explanation) the following:

• Up to two homeworks
• Up to two group works
• Up to 5 Canvas self-checks
• One quiz

Academic Integrity and "AI" Policy

Every student is expected to turn in their own work for all assignments, exams, and quizzes in this class.  This does not mean you may not discuss how to solve problems with your classmates.  A good rule of thumb, that I have stolen from the university's talented youth mathematics program, is this: if you discuss a homework problem with someone else and think you have a solution, then do something else for a half hour. Work on another problem or another class, get a snack, go for a walk, whatever.  If you can then write up a solution to the problem (without referencing any notes or code from your discussion) you must have understood the solution, and if you can't then your discussion didn't directly influence your eventual solution. 

Oral Presentations

As in real life, each student is ultimately responsible for understanding any submitted work in this class.  To encourage students not to submit work they do not understand, each week the TAs will randomly select some students to orally present and explain their homework solutions, and grades for these oral presentations will be used in place of any written work.  Students will be informed of their selection through the gradescope comment interface, and will be expected to respond to this request within 48 hours of the release of grades.  Failure to respond to the request will result in a score of zero for the homework.  This random selection will be performed in a way that guarantees a minimum of two oral presentations per student.

Penalty for Academic Misconduct

The University Student Conduct Code defines scholastic dishonesty as: submission of false records of academic achievement; cheating on assignments or examinations; plagiarizing; altering, forging, or misusing a University academic record; taking, acquiring, or using test materials without faculty permission; acting alone or in cooperation with another to falsify records or to obtain dishonestly grades, honors, awards, or professional endorsement. In this course, a student responsible for scholastic dishonesty will be assigned a penalty of an "F" or "N" for the course. If you have any questions regarding the expectations for a specific assignment or exam, please ask us.

Classroom atmosphere expectations

I want this to be a class where everyone feels comfortable asking questions (which is how we learn!) and contributing to discussions.  In order for this to happen, it is important for us all to respect and learn from one another.  Here are some things to keep in mind when interacting with fellow students and course staff:

We all have different experience levels.  Some students may have encountered some materials in this class before, and might make it look like a problem is easy, where other students might find the material new and intimidating.  Please keep in mind that no one knows all of the material, and everyone struggles at some point.  When someone is struggling and you help them move forward, they will remember and you will learn more than if you try to hold them back.  When you are struggling, just remember that just because you haven't learned something yet doesn't mean you can't learn it now.

We all have different identities.  As part of respectful dialog, please think how your comments could impact others in your group. Refer to others as they prefer to be referred to (including, if referring to them in the third person, using any preferred pronoun they choose to indicate).

Part of respecting each other is helping to keep each other safe and healthy.  If you are not feeling well, please do not attend lecture.  All class lecture slides will be posted on Canvas, and lecture recordings will be posted to Canvas.

Other policies and information

Disability Accommodations

The University of Minnesota views disability as an important aspect of diversity, and is committed to providing equitable access to learning opportunities for all students. The Disability Resource Center (DRC) is the campus office that collaborates with students who have disabilities to provide and/or arrange reasonable accommodations. 

• If you have, or think you have, a disability in any area such as, mental health, attention, learning, chronic health, sensory, or physical, please contact the DRC office on your campus (612.626.1333) to arrange a confidential discussion regarding equitable access and reasonable accommodations. 
• Students with short-term disabilities, such as a broken arm, can often work with instructors to minimize classroom barriers. In situations where additional assistance is needed, students should contact the DRC as noted above.
• If you are registered with the DRC and have a disability accommodation letter dated for this semester or this year, please contact your instructor early in the semester to review how the accommodations will be applied in the course. 
• If you are registered with the DRC and have questions or concerns about your accommodations please contact your (access consultant/disability specialist).

Additional information is available on the DRC website: https://diversity.umn.edu/disability/  or  students may email drc@umn.edu with questions.

Academic Freedom and Responsibility

Academic freedom is a cornerstone of the University. Within the scope and content of the course as defined by the instructor, it includes the freedom to discuss relevant matters in the classroom. Along with this freedom comes responsibility. Students are encouraged to develop the capacity for critical judgment and to engage in a sustained and independent search for truth. Students are free to take reasoned exception to the views offered in any course of study and to reserve judgment about matters of opinion, but they are responsible for learning the content of any course of study for which they are enrolled.

Reports of concerns about academic freedom are taken seriously, and there are individuals and offices available for help. Contact the instructor, the Department Chair, your adviser, the associate dean of the college, or the Vice Provost for Faculty and Academic Affairs in the Office of the Provost.