Exams
As stated on the syllabus: "The midterm and final exams are open note.
Students may consult any printed or handwritten materials brought into
the exam, and any static content stored locally on the student's own
device or on a Dickinson College server. Web searches are not
permitted. No content stored outside the College network may be
consulted. Electronic devices may only be used for browsing static
content. Devices may not be used to perform any other type of
computation."
Exams will consist of some or all of the following: true-false
questions, short answer questions, and questions requiring longer
answers and/or mathematical proofs.
Technically, exams may ask questions about anything covered in
class, assigned readings, handouts or homework assignments. In
practice, however, a strong majority of questions will be related to
homework questions, or to examples covered during a class lecture.
Note: When proving results in exams for this course, you may
assume, without proof, any facts that were stated or proved in class
or in the textbook (unless the question specifically states
otherwise). For example, if it was stated or proved in class that a
certain computational problem is undecidable, NP-hard, or NP-complete,
you may use this fact in your proofs. However, you must clearly state
any fact that you use in this way.
Exam 1
Exam 1 covers material from textbook chapters 1-9 inclusive. It is
very likely to contain at least one question asking for a proof of
uncomputability via reduction, one question asking you to use the
pumping lemma to prove non-regularity of a language, and one question
asking you to convert an nfa to a dfa.
Exam 2
Exam 2 covers material from textbook chapters 10-14 inclusive. Likely
questions include: estimating the complexity of a Python program;
proving that various problems are in Poly, PolyCheck/NPoly,
NPComplete, NPHard, Exp, etc.; proving there is a polynomial time
reduction from one problem to another; giving examples of problems
that are in or out of the common complexity classes.
Final Exam
The final exam is cumulative, covering all topics with approximately
equal emphasis. The style of the exam will be similar to the two
in-class exams.
Additional details, added 4/30/15: The final exam will consist of ten
15-point questions. Your score will be computed from your best EIGHT
questions. In other words, you can skip up to two questions if you
want, and still get 100%. (Yes, if you hate the pumping lemma, you
can skip the pumping lemma question!!)