Skip to the content.


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

Students may not

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.


  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:

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:

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.