Course Syllabus

CSCI 4011 Inherent Limitations of Computer Programs
(Summer 2020)

Instructors and Schedule

Instructor: Nick Hopper (email: hoppernj@umn.edu)

Teaching Assistant: Nabil Khan (email: khan0096@umn.edu)

Our office hours (complete with Zoom links) are scheduled on the course Google Calendar:

Course Description

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 two 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 -- a language -- 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.  We'll repeat this process a second time, defining a new model of programs, the pushdown automaton, and again prove that there are some problems that we can solve with real programs that we can't program a pushdown automaton to solve.   Finally, we'll develop a slightly more sophisticated model of a program, the Turing Machine, and we'll prove that any program we can write for any known computer can be converted to a Turing Machine program, and we'll also slightly refine our model of a problem to include computation and decision problems.
   
   
2. Un-Computability and Complexity: In the second unit, we will start by provig 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.  We'll see how to apply these methods to prove that many important problems about computing have no general solution.  Then 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:
Once you complete this course you 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 videos 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 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.

Textbook

The required textbook for this course is Michael Sipser's Introduction to the Theory of Computation, 3rd edition.  At the current time, the 1st edition of this textbook is available online (as scans only) through the university library.  (click the "login" button in the upper right hand corner, select "University of Minnesota" from the drop down, and log in to your UMN Internet account)  It is not clear how many concurrent licenses are available to this content, so if you use this resource, please promptly "return" the book after obtaining the reading for a given module.

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; so you should expect to do about 12×15 = 180 hours of work in this course.  Because of the 8-week summer term timeline, that means you should expect to spend about 20-24 hours per week on the course.  A rough breakdown per week would be:

• Viewing recorded lectures/videos: 3-4 hours
• Required weekly readings: 4-6 hours
• Group work and discussions: 3-4 hours
• Bi-weekly checkins: 2 hours
• Homework: 5-7 hours

Grading

Grading for the class will be based on six components:

• 7 Homeworks (30%): We will have weekly homeworks, to be turned in by 1159pm CDT each Monday.  Homeworks will consist of 4 problems, posted in Canvas. 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 start on a separate page to allow the grader to find and grade each problem. Homework problems will be graded on a 10-point scale as follows:
  

  10 points	The solution is exemplary and could be used in a textbook or to explain the solution to other students.
  8-9 points	The solution meets expectations. It has no major errors or omissions, but could be more clearly explained or include more details.
  5-7 points	The solution needs revision, but has the "right idea"
  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.

  Homeworks can be scanned PDFs or produced with a typesetting system such as LaTeX or Google Docs, but should be submitted as PDFs in Canvas.
  
  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 Wednesdays at Noon CDT, at which point homeworks that have not been submitted are worth 0 points.
  
  Dropping Homeworks. Your two lowest homework scores will be dropped.

• Group Participation (10%): Every student will be assigned to a group that has compatible availability.  Every week there will be a discussion thread where you are expected to discuss example problems related to the readings and videos for that week.  We will tally your contributions to these discussions, and if you make at least four productive contributions to each discussion, you will receive full credit for the week.  Examples of productive contributions include but are not limited to: proposing a solution to a problem; asking a clarifying question about someone else's solution; answering a clarifying question; pointing out a problem in a proposed solution; suggesting an improvement.
• Reading Quizzes (10%): Every assigned video will have an associated 5-point Canvas quiz; you can retake the quiz as many times as you want but must get 4/5 points on the quiz to proceed to the next video in the module.
• Check-in Attendance (10%): Every group will have two check-in Zoom meetings with the instructor (and possibly a few other groups) each week, during which we can discuss your group work, work on a few more examples, further clarify any questions you might have, and so on.  You'll get one point for each meeting you participate in, and you can miss up to two meetings.
• Take-home Midterm (20%): We will have a 36-hour take-home midterm, released at 9am CDT on Tuesday, July 7 and due at 9pm CDT on Wednesday, July 8th.  No late submissions will be accepted.
• Take-home Final (20%): The 36-hour take-home final exam will be released at 9am CDT on Thursday, July 30th and due at 9pm CDT on Friday, July 31st.  No late submissions will be accepted.  The final exam is comprehensive, but will focus more on the subjects covered in the second half of the course.

Composite averages from these categories will be converted to letter grades as follows:

Other policies and information

Academic Integrity Policy

Every student is expected to turn in his or her own work for all assignments, and exams in this class.  This is not meant to block general discussion of HOW to do homework problems.   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.

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.

Makeup Work for Legitimate Absences

Students will not be penalized for absence during the semester due to unavoidable or legitimate circumstances. Such circumstances include verified illness, participation in intercollegiate athletic events, subpoenas, jury duty, military service, bereavement, and religious observances. Such circumstances do not include voting in local, state, or national elections. For complete information, please see: http://policy.umn.edu/education/makeupworkLinks to an external site..

Appropriate Student Use of Class Notes and Course Materials

Taking notes is a means of recording information but more importantly of personally absorbing and integrating the educational experience. However, broadly disseminating class notes beyond the classroom community or accepting compensation for taking and distributing classroom notes undermines instructor interests in their intellectual work product while not substantially furthering instructor and student interests in effective learning. Such actions violate shared norms and standards of the academic community. For additional information, please see: http://policy.umn.edu/education/studentrespLinks to an external site..

Sexual Harassment

"Sexual harassment" means unwelcome sexual advances, requests for sexual favors, and/or other verbal or physical conduct of a sexual nature. Such conduct has the purpose or effect of unreasonably interfering with an individual's work or academic performance or creating an intimidating, hostile, or offensive working or academic environment in any University activity or program. Such behavior is not acceptable in the University setting. For additional information, please consult Board of Regents Policy: https://regents.umn.edu/sites/regents.umn.edu/files/policies/Sexual_Harassment_Sexual_Assault_Stalking_Relationship_Violence.pdfLinks to an external site.

Equity, Diversity, Equal Opportunity, and Affirmative Action

The University provides equal access to and opportunity in its programs and facilities, without regard to race, color, creed, religion, national origin, gender, age, marital status, disability, public assistance status, veteran status, sexual orientation, gender identity, or gender expression. For more information, please consult Board of Regents Policy: http://regents.umn.edu/sites/regents.umn.edu/files/policies/Equity_Diversity_EO_AA.pdfLinks to an external site..

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/Links to an external site.  or  students may email drc@umn.edu with questions.

Mental Health and Stress Management

As a student you may experience a range of issues that can cause barriers to learning, such as strained relationships, increased anxiety, alcohol/drug problems, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may lead to diminished academic performance and may reduce your ability to participate in daily activities. University of Minnesota services are available to assist you. You can learn more about the broad range of confidential mental health services available on campus via the Student Mental Health Website: http://www.mentalhealth.umn.eduLinks to an external site..

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.