Cs 6515 Updated Actual Exam Questions Correct Answers Graded A Plus.pdf 1. Document Information C

CS 6515 UPDATED ACTUAL EXAM QUESTIONS CORRECT ANSWERS GRADED A PLUS




Question:
What is a NP problem?

Answer:
NP = Non-Deterministically Polynomial A problem where the Solution can be VERIFIED in
Polynomial-Time



Question:
What are differences in P and NP?

Answer:
All P problems are in NP but all NP problems are not in P. P is a subset of NP. Problems may be
verifiable in Polynomial-Time but not solvable in Polynomial-Time



Question:
What are NP-Complete Problems?

Answer:
The hardest problems in the NP class. A problem is NP-Complete if it is in NP and in NP-Hard.



Question:
What are NP-Hard problems?

Answer:
A problem at least as hard as every problem in the class NP. A problem is NP-Hard if all other
problems in NP can be polynomially reduced to it. NP-Hard problems don't have to be NP problems.

, Question:
What is the difference between NP-Complete and NP-Hard?

Answer:
NP-Complete problems are the hardest in the set NP. NP-Hard is not necessarily in NP. NP-Hard
problems are at least as hard as everything in the set NP.



Question:
What is a clause edge?

Answer:
An edge between vertices in the same clause



Question:
What is a variable edge?

Answer:
An edge between complimentary vertices x and x' have a variable edge between them.



Question:
How to reduce 3SAT to Independent Set?

Answer:
1. Create a graph representation of 3SAT input 1 vertex for each literal and each clause. 2. Add
Clause Edges An edge between each literal in a clause 3. Add variable edges An edge between x and
x'



Question:
What vertices do we choose to be in the IS?

Answer:
1. No Clause Edges between vertices. Vertices cannot be neighbors of each other. 2. No Variable
Edges Vertices cannot be compliment of each other x and x' cannot both be in IS.