|
|
|
CSci 4011: Inherent limitations of
computer programs
Spring 2009
4 Credits
Lecture: T Th 2:30-3:45, Phys 170
Recitations:
Section 2: W
2:30-3:20, FordH 150
Section 3: W
3:35-4:25, AmundH 124
Section 4: W 1:25-2:15, AmundH 240
Instructor:
Nick Hopper
EECS 4-211
hopper AT cs.umn.edu
TAs:
Adam Isom
aisom AT cs.umn.edu
Sheng-Wen Wang
wangx549 AT umn.edu
Office Hours:
Our regular
office hours will be:
|
M
|
T
|
W
|
Th
|
F
|
Nick (EECS 4-211)
|
2:00-3:30
|
3:45-5:00
|
4:30-6:00
|
3:45-5:00
|
|
Adam (EECS 2-209)
|
|
11:15-12:15
|
|
11:15-12:15
|
|
Sheng-Wen (EECS 2-209)
|
11:00-12:00
|
|
|
|
1:00-2:00
|
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", 2nd edition, ISBN 0534950973. It is
available
from the campus bookstore as well as various online vendors. Make
sure
that you have the newer 2nd edition and not the first, since some
homework assignments will come from the text.
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.
- 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.
- 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.
- 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 1901 and 1902 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 prerequisites for this
course are CSci 1902 and CSci 2011.
From CSci 1901 and 1902 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 acheives 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 wholely
unreasonable
has occurred will the instructor intervene. Furthermore, there is
a limit of ten days from the due date 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 you and at least one other member of your group will be assigned
an additional problem to solve, and then present the solution to your
group in recitation. We will then choose one problem to be
written up and handed in by each group. These writeups, one per
group, should be handed in by the beginning of the next Tuesday class
period. Solutions will be graded on the same scale as
homeworks. Even if the writeup is not the problem you were
assigned, you are responsible for helping your group to produce the
best possible solution.
- 6 Quizzes (25%) We will
have six quizzes during (Wednesday) recitation sections, the dates of
which are already
marked on the course schedule. Each quiz will be graded on a scale
from 0-10. We will drop each student's lowest quiz score.
On the remaining 5 quizzes, a student must score at least 30/50 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:
92
- 100
|
A
|
90
- 92
|
A-
|
86
- 90
|
B+
|
82
- 86
|
B
|
80
- 82
|
B-
|
76
- 80
|
C+
|
70
- 76
|
C
|
66
- 70
|
C-
|
63
- 66
|
D+
|
59
- 63
|
D
|
0
- 59
|
F
|
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.
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.
|
|
