Exams

The midterm and final exams are open note and open web. Students may consult any printed or digital materials and may perform web searches. Students are encouraged to use all appropriate tools, including JFLAP, IDLE, Python programs, and existing content on programming websites and forums. However, it is not permitted to seek help from other humans either directly or via an online forum.

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.

Ample extended time will be available to all students and the ADS Test-Related Guidance will be followed.

Students with academic accommodations receive extra time in the normal way. For example, if the stated time to submit the exam is 24 hours, a student who normally receives time-and-a-half for tests will have 36 hours to complete the exam.

Exams will be provided in Microsoft Word PDF format. Answers can be provided in any reasonable format, including Microsoft Word, PDF, or handwritten solutions that have been scanned/photographed.

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: Of course, it might not include all of the above types of questions, and there will be other questions too. The exam begins at the start of class on the designated day of the exam (10:30 a.m., Thursday March 11, 2021). The exam will be of a length that could typically be completed in a 75-minute class session. However, all students will have 24 hours to complete and submit the exam to Moodle. Therefore, the deadline for submission is 10:30 a.m. Eastern time on 3/12/21. Late submissions will be penalized by 5% per hour.

The exam can be downloaded from Moodle via a link that will become active five minutes before the start of the exam.

Exam solutions should be submitted to the Exam 1 submission link on Moodle.

All communication with the instructor should be via Microsoft Teams, either via private chat message or by posting to the Exams channel, which will be visible to all members of the class. Any announcements or clarifications by the instructor will be posted to the Exams channel.

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.

The exam begins at the start of class on the designated day of the exam (10:30 a.m., Tuesday April 27, 2021). The exam will be of a length that could typically be completed in a 75-minute class session. However, all students will have 24 hours to complete and submit the exam to Moodle. Therefore, the deadline for submission is 10:30 a.m. Eastern time on 4/28/21. Late submissions will be penalized by 5% per hour.

The exam can be downloaded from Moodle via a link that will become active five minutes before the start of the exam.

Exam solutions should be submitted to the Exam 2 submission link on Moodle.

All communication with the instructor should be via Microsoft Teams, either via private chat message or by posting to the Exams channel, which will be visible to all members of the class. Any announcements or clarifications by the instructor will be posted to the Exams channel.

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 exam begins at the start of the designated exam slot for this course (2:00 p.m., Thursday May 13, 2021). The exam will be of a length that could typically be completed in 120 minutes. However, all students will have 48 hours to complete and submit the exam to Moodle. Therefore, the deadline for submission is 2:00 p.m. Eastern time on 5/15/21. Late submissions will be penalized by 5% per hour.

The exam can be downloaded from Moodle via a link that will become active five minutes before the start of the exam.

Exam solutions should be submitted to the Final Exam submission link on Moodle.

All communication with the instructor should be via Microsoft Teams, either via private chat message or by posting to the Exams channel, which will be visible to all members of the class. Any announcements or clarifications by the instructor will be posted to the Exams channel.