Foundations of Computing Theory Final
Tuesday, February 19, 8:00am-10:00am, in GOL-2590.
Review
Monday, February 18, 3:15pm-4:45pm, in GOL-3560.
Important
Make sure that you handle all grading issues before the FCT final!
Topics
The emphasis of the final is on new stuff (described below)
and on overview questions.
You do need to know the main points of Chapter 1, but not the details.
For example, you should know that NFAs are equivalent to DFAs, but
you will not be required to apply the subset construction.
New stuff
- Context-free languages: Chapter 2.1, 2.2, and 2.3.
Chapter 2 notes, homework, and what we did in class
You may skip the proof idea and proof of Lemma 2.27.
- Turing machines: Chapter 3,
Chapter 3 notes, homework, and what we
did in class. You may skip the subsections on enumerators and on
Hilbert's problems.
- Decidability: Section 4.1, Chapter 4 notes on decidability,
homework, and what we did in class.
- Undecidability: Chapter 4 notes on undecidability, Chapter 5 notes,
homework, and what we did class. Skip Post's correspondence problem.
- Complexity: Complexity notes, homework, and what we did
in class.
Notes
-
The final will be closed book and notes,
but you may bring one sheet of letter-sized paper with your own
hand-written notes. You may write on both sides.
-
Like the midterm, the final will consist of five or six questions
of equal weight.
Your lowest question score won't count.
Since it is often hard
to judge how well you did on a question, make sure to answer all
questions.
-
The final can not be made up except for real emergencies in which case
proper documentation (like a doctor's note) will be required.
You should notify me of your absence as soon as possible (in almost
all cases, this will be well before the final).
Oversleeping, cars that don't start etc. do not constitute a valid excuse.
-
Calculators, cell phones, PDAs etc. are not allowed.
I suggest that you bring a watch.
-
You may only leave the room after you turn in your exam.
-
The final is worth 25% of your course grade.
-
To get some idea of the format of the final and the level of
difficulty of the questions, you can look at
some sample final questions.
This is just to get some idea. The sample questions do not guarantee
anything about the topics of the questions on your final and
they do not guarantee the exact level of difficulty
of the questions on your final.
-
And here are the
sample final questions with
answers.
VCSG 700