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." In particular, note that you may not use JFLAP and you
may not execute or experiment with any Python programs.
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.
Notes:
- 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.
- When describing Turing machines and finite automata, you may
use any generally-accepted notation, including the textbook's
notation or JFLAP notation.
Exam 1
Exam 1 covers material from textbook chapters 1-9 inclusive. It is
likely to contain questions asking you to:
- prove the uncomputability of a problem via reduction and/or via one of
the variants of Rice's theorem
- design or explain Turing machines and/or finite automata that
accept a certain language or perform a given computation
- use the pumping lemma to prove non-regularity of a language
- convert an nfa to a dfa
Of course, it might not include all of the above types of questions,
and there will be other questions too.
A sample exam and its solutions are provided on Moodle.
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, Expo, 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.
A sample exam and its solutions are provided on Moodle.
Final Exam
The final exam is cumulative, covering all topics in chapters 1-14
with approximately equal emphasis. The style and content of questions
on chapters 1-14 will be similar to the two in-class exams.
Chapters 15-17 will be examined too, but the style of questions will
be less rigorous: you are expected to have read and understood this
material, but detailed calculations and proofs based on chapters 15-17
are not required. The ungraded questions in Assignment J are typical
examples of questions that could be asked about chapters 15-17.