Course Syllabus

CSci 4011: Inherent Limitations of Computer Programs

Spring 2018
4 Credits
Lecture: T Th 2:30-3:45, Bruininks 220
Recitations:
    Section 2: F 12:20 - 1:10, Ford 150
    Section 3: F  1:25  - 2:15, Amundson 240
    Section 4: F  2:30  - 3:20, Amundson 240

Instructor:
Nick Hopper
Keller 4-211
hoppernj AT cs umn edu

TAs:

Zane Smith
smit9474 AT umn edu

Nathan Taylor
taylo740 AT umn edu

Office Hours:
Office hours are shown on the course google calendar:

If you want to speak with one of us about the course and can't make one of the scheduled times, please send an email and we'll schedule a different meeting. 


Textbooks:
The required textbook for this course is Michael Sipser's "Introduction to the Theory of Computation", 3rd edition, ISBN 0534950973.  It is available from the campus bookstore as well as various online vendors. 

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 lectures for the class will feature lots of examples of proofs.  The 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.  Thus you can expect that in this class, understanding the definitions given in class will play an important role in doing well on quizzes and exams.

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 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.

Grading:
Grading for the class will be based on five components:

• 12 Homeworks (20%): we will have weekly homeworks, to be turned in at the beginning of  class each Tuesday.  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:
  
  

  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

  
  
  Each week we will also have one extra credit problem.  These challenging problems count half as much as a regular problem.  An attempted extra credit solution will only receive points if it achieves a grade of 7/10 - you should only work on these problems after you have solved the regular problems in a given week.
  
  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.
  
  Due dates for all assignments are strict: all homeworks must be received at the very start of the class in which they are due in order to receive full credit. Late homeworks turned in before 6pm on Wednesday will be considered for 50% credit, and after 6pm on the day after it is due, a homework is worth 0 points, with no exceptions. 
  
  Keep a copy of each of your submissions as evidence that you have indeed submitted each assignment. Do not ever put your assignment under the instructor's office door: this is a certain way to receive zero points for an assignment.
  
  Homework grading is performed by the TAs. If you have a question about homework grades, address it to the TAs. 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, such will not be considered.
  
  
• Group Work (5%): In your recitation 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 (25%) We will have six quizzes during (Friday) recitation sections, the dates of which 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:
 

The dates for all quizzes and exams are currently marked on the class schedule.  Please be sure to make note of them, because there will be no makeup quizzes or exams, except in extraordinary and documentable circumstances.

To deal with the fact that students can have complicated lives and Minnesota can have difficult weather, each student's highest 5 quiz scores, 10 group work scores, and 10 homework scores will be considered in computing final grades.

Academic Integrity Policy:

Every student is expected to turn in his or her own work for all assignments, exams, and quizzes in this class.  This is not meant to block general discussion of HOW to do homework problems.

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.