About the CS:5340 Midterm
- The midterm for CS:5340 will be on Fri, Oct 6th from 6:30 pm to 8:30 pm in
203 Becker Communication Studies Building (BCSB).
This is an open notes (book) exam, so feel free to bring
books, handwritten notes, printouts of online notes and webpages, etc., to the exam.
During the exam you will not have access to any electronic devices and you will not be
able share any material with classmates.
The exam is worth 25% of your grade and will be graded out of 250
points.
It will be over the material in Chapters 1 (skip Section 1.7), 2, 3 (Sections
3.1-3.3 only), and 4 (Section 4.1 only).
- There will be 4 problems on the exam. Here are more details about each
problem.
- (100 points)
I will give you 10 complexity-theoretic claims and for each claim, you will
have to say whether the claim is known to be true,
known to be false, or not known to be either.
If your answer is true or false, you will have to
provide a 1-sentence justification for your answer.
- (50 points)
You will be asked to show that a certain (given) language is uncomputable.
This will be similar to Problems 2-3 in HW2.
- (50 points)
You will be asked questions that will help you show your understanding
of the proof of the Cook-Levin Theorem (Theorem 2.10, Lemma 2.11).
- (50 points)
You will be asked questions that will help you show your understanding of the
use of diagonalization in the proofs of the
time hierarchy theorems (Theorem 3.1 and the proof of the non-deterministic hierarchy theorem
due to Fortnow and Santhanam) and the proof of Ladner's Theorem on the existence of "NP-intermediate" languages.