CS6515 Graduate Algorithm Exam 3 Practice
Questions with Answers 2026 Guide
1. What does "efficiently" mean Polynomial in the input size
in the context of NP-com-
pleteness?
2. What is the class NP? The set of search problems for which we can verify a solution in
polynomial time
3. What is the class P? The set of search problems that we can solve in polynomial time
4. What is the relationship be- P †N P
tween P and NP?
P is certainly a subset of NP, but it's unknown whether P = NP.
Phrased another way, if NP is all search problems, and P is all
search problems that can be solved in polynomial time, then P is
a subset of NP.
5. How long does it take to veri- O(nm), as each clause has up to n literals, and there are m
fy an assignment to SAT? clauses.
This implies that SAT is in NP.
6. How long does it take to veri- O(m). For each of the m edges (u, v), check that color(u) !=
fy a k-coloring? color(v).
7. How long does it take to ver- O(m log n).
ify whether T is an MST of a
graph G? 1. Run BFS on T to check that it is in fact a tree, in O(n + m)
2. Run Kruskal's or Prim's on G and check that the weight of the
produced tree is that same as that of T, in O(m log n)
Note that this implies that not only is MST in NP, but also P. We
can produce the MST of a graph in O(m log n) as well.
8. Is knapsack in NP or P?
1/9
, CS6515 Graduate Algorithm Exam 3 Practice
Questions with Answers 2026 Guide
Neither.
It's not in NP as given a solution, we don't know whether the sum
of the values is in fact maximized.
It's not in P as the best algorithm we have runs in O(nB), where
B is the budget. B is exponential in the size of the budget, log B.
(This is pseudopolynomial).
9. Is knapsack search in NP? Yes. Sum the n items, check that the total weight <= B and total
value >= g.
10. If knapsack search were solv- Binary search on [1, V] where V = sum of all item values. For
able in polynomial time, how each candidate goal g, use the knapsack search black box to
could we use it to solve the determine whether g is achievable. We run a polynomial time
knapsack optimization prob- algorithm log V times.
lem?
11. What is NP-complete? This is the set of the hardest problems in NP. If P != NP, then these
problems would lie in NP but not P.
If a problem A is NP complete, then 1) it is in NP 2) if a polynomial
time algorithm for A exists, then that algorithm could be used to
solve all NP complete problems.
If a problem A is NP complete, then any problem in NP can be
reduced to it. A is at least as hard as any problem in NP.
12. What does it mean to reduce A ’B means B >= A, B is at least as hard as A.
a problem A to B?
If we can solve B in polynomial time, we can use that algorithm
to solve A in polynomial time.
Solving A would be no harder than solving B, because if we could
2/9
Questions with Answers 2026 Guide
1. What does "efficiently" mean Polynomial in the input size
in the context of NP-com-
pleteness?
2. What is the class NP? The set of search problems for which we can verify a solution in
polynomial time
3. What is the class P? The set of search problems that we can solve in polynomial time
4. What is the relationship be- P †N P
tween P and NP?
P is certainly a subset of NP, but it's unknown whether P = NP.
Phrased another way, if NP is all search problems, and P is all
search problems that can be solved in polynomial time, then P is
a subset of NP.
5. How long does it take to veri- O(nm), as each clause has up to n literals, and there are m
fy an assignment to SAT? clauses.
This implies that SAT is in NP.
6. How long does it take to veri- O(m). For each of the m edges (u, v), check that color(u) !=
fy a k-coloring? color(v).
7. How long does it take to ver- O(m log n).
ify whether T is an MST of a
graph G? 1. Run BFS on T to check that it is in fact a tree, in O(n + m)
2. Run Kruskal's or Prim's on G and check that the weight of the
produced tree is that same as that of T, in O(m log n)
Note that this implies that not only is MST in NP, but also P. We
can produce the MST of a graph in O(m log n) as well.
8. Is knapsack in NP or P?
1/9
, CS6515 Graduate Algorithm Exam 3 Practice
Questions with Answers 2026 Guide
Neither.
It's not in NP as given a solution, we don't know whether the sum
of the values is in fact maximized.
It's not in P as the best algorithm we have runs in O(nB), where
B is the budget. B is exponential in the size of the budget, log B.
(This is pseudopolynomial).
9. Is knapsack search in NP? Yes. Sum the n items, check that the total weight <= B and total
value >= g.
10. If knapsack search were solv- Binary search on [1, V] where V = sum of all item values. For
able in polynomial time, how each candidate goal g, use the knapsack search black box to
could we use it to solve the determine whether g is achievable. We run a polynomial time
knapsack optimization prob- algorithm log V times.
lem?
11. What is NP-complete? This is the set of the hardest problems in NP. If P != NP, then these
problems would lie in NP but not P.
If a problem A is NP complete, then 1) it is in NP 2) if a polynomial
time algorithm for A exists, then that algorithm could be used to
solve all NP complete problems.
If a problem A is NP complete, then any problem in NP can be
reduced to it. A is at least as hard as any problem in NP.
12. What does it mean to reduce A ’B means B >= A, B is at least as hard as A.
a problem A to B?
If we can solve B in polynomial time, we can use that algorithm
to solve A in polynomial time.
Solving A would be no harder than solving B, because if we could
2/9
