Exams

As stated on the course syllabus, the midterm and final exams are “closed book with note sheet.” This webpage provides additional guidance on exams for this course.

• It will be possible to retake an exam under certain conditions. See the separate Exam retakes page.

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

• You may not consult any printed, written, electronic, or other materials. Exceptions: you may bring into the exam one page of handwritten notes (one side of US letter sized paper only) for Exams 1 and 2; for the final exam, two sides of handwritten notes are permitted.

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

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

• Practice exams are available. (These are actually exams from an earlier instance of the course, in which exams were open note. The nature of the questions will be adjusted a little for this semester because the exams are now closed book.)

  • Written exam 1 practice, solution
  • Written exam 2 practice, solution
  • Final exam practice, solution

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.

The duration of the exam is 75 minutes, and there will be questions worth a total of approximately 75 points on the exam. So you should budget your time at the rate of about one point per minute. Try to allocate your time wisely: spend only about 10 minutes on a 10-point question, and about 5 minutes on a 5-point question, and so on.

One side of handwritten notes are permitted.

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.

O ne side of handwritten notes are permitted.

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.

The final exam is in two parts with one bathroom break between parts: The exam consists of two parts: part A and part B. You must turn in your final answers for part A before receiving the questions for part B. You may choose to exit the exam room after turning in part A and before receiving part B. No other exits are permitted (except for permanent departure after turning in the final answers to part B). Notify the instructor if you need alternative arrangements for medical reasons. See the sample exam cover sheet for additional details.