Design and Analysis of Algorithms · Unit 8 · 5 hrs
NP Completeness
Exam-focused notes for NP Completeness (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity
- Complexity Classes: P, NP, NP-Hard and NP-Complete
- NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem, Proofs of NP Completeness (CNF-SAT, Vertex Cover and Subset Sum)
- Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem
Complexity Classes
Define class P and NP problem. Why do we need approximation algorithms? Justify. [5]
Class P (Polynomial time) is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, i.e., in O(n^k) time for some constant k, where n is the size of the input. - These are considered "efficiently solvable" problem...
Full solved answer →Explain in brief about the complexity classes P, NP and NP Complete. [5]
Definition: P is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, i.e., in O(n^k) steps for some non-negative integer k, where n is the size of the input. - These problems are considered "fast" or efficientl...
Full solved answer →Explain in brief about the classes P, NP, and NP complete with examples. [5]
--- Definition: P is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, i.e., in O(n^k) for some constant k. - These are considered tractable (efficiently solvable) problems. Examples: - Sorting (Merge Sort: O...
Full solved answer →Approximation Algorithms
Explain the approximation algorithm for vertex cover of a connected graph with an example. [5]
A Vertex Cover of a graph G = (V, E) is a set of vertices C ⊆ V such that every edge in G is incident to at least one vertex in C. The optimization problem is to find the vertex cover with the fewest vertices (optimal vertex cover C\). Since finding the exa...
Full solved answer →Explain the approximation for solving vertex cover with a suitable example. [5]
A vertex cover of an undirected graph G = (V, E) is a subset V' ⊆ V such that for every edge (u, v) ∈ E, at least one of u or v belongs to V'. The optimization problem is to find the vertex cover with the fewest vertices. The approximation problem is to fin...
Full solved answer →NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem, Proofs of NP Completeness
State cooks theorem. Discuss about problem reducibility. [5]
Statement: Cook's theorem states that the Boolean Satisfiability Problem (SAT) is NP-Complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfia...
Full solved answer →Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete". [5]
A problem X is called NP-complete if it satisfies both of the following conditions: 1. X belongs to NP: The problem X can be verified in polynomial time. That is, given a candidate solution (certificate), we can check whether it is correct in polynomial tim...
Full solved answer →Write short notes on: a. NP Hard Problems and NP Completeness b. Problem Reduction [5]
--- A problem is called NP-Complete if it satisfies two conditions: 1. It belongs to the class NP (the solution can be verified in polynomial time). 2. Every other problem in NP can be reduced to it in polynomial time (it is NP-Hard). NP-Complete problems a...
Full solved answer →Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity
Define tractable and intractable problem. Illustrate vertex cover problem with an example. [5]
--- A problem is said to be tractable if it can be solved in polynomial time, i.e., its time complexity is O(n^k) for some constant k. These problems are considered efficiently solvable in practice. Examples: Sorting (O(n log n)), Binary Search (O(log n)), ...
Full solved answer →Make Unit 8 stick
Practice CSC325 with flashcards & quizzes