Exams

The midterm and final exams are “open note.” As stated on the course syllabus, this means “you can consult your own notes, the textbook, and course materials.” This webpage provides additional guidance on exactly what is permitted.

Students may

• consult any printed or written materials;
• consult an electronic copy of the textbook;
• consult any content on the official course webpages, including Moodle (this includes the homework solutions and the textbook’s Python programs);
• use JFLAP, IDLE, and any other reasonable development environment for writing Python programs (e.g. PyCharm, VSCode).

Students may not

• perform web searches;
• consult online material other than that listed above;
• consult other humans or generative AI tools such as chatbots.

All solutions must be written by hand on blank paper and turned in at the end of the exam.

Technically speaking, any material covered in any lecture, reading, or homework assignment is eligible to appear in the midterm or final exams. In practice, most exam questions will be similar to a homework question, an example done in class, or other assigned practice questions.

Notes:

1. 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.
2. 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 the three reduction techniques (reduction recipe, explicit Python programs, 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.

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.

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 midterm 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.

As with all Dickinson final exams, you have three hours to complete the exam. The final exam will have questions worth approximately 120 points, with the usual expectation that a well-prepared student would require about one minute per point. Therefore, the final exam should have somewhat less time pressure than the midterm exams.