[go: up one dir, main page]
Scribd
Upload
28 views6 pages

Algo A5

Uploaded by

mustabshirah.nayer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views6 pages

Algo A5

Uploaded by

mustabshirah.nayer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

National University of Computer & Emerging Sciences, Karachi

Fall-2020 Department of Computer Science


Assignment 5
Due: 25th December 2020

Max Marks: 60 Points

Question # 1 20 Points

Explain in your own words

(a) What is meant by P and NP Problems? Explain P = NP


(b) Why it is important to find approximate solutions for NP Complete Problems
(c) What is the difference between NP Complete and NP Hard
(d) A problem that is solvable in time complexity of 𝑇(𝑛) = 3 ∗ 𝑛𝑛 and space complexity of 𝑆(𝑛) =
𝑛2 and it can be validated in 𝑇(𝑛) = 2𝑛 time. Is it a NP-Complete or NP-Hard? Explain

Question #2

Consider the following APPROX-VERTEX-COVER algorithm. Proof that this algorithm is 2-


approximation method for VERTEX-COVER. 10 Points

APPROX-VERTEX-COVER(G)
C = ∅;
E’=G.E;
while(E’ ≠ ∅ ){
Randomly choose a edge (u,v) in E’, put u and v into C;
Remove all the edges that covered by u or v from E’
}
Return C;

Question 3 10 Points

An Instance (𝑋, 𝐹) of the set-covering problem consists of a finite set X and a family F of subset
of X, such that every element of X belongs to at least one subset of F:
𝑋 = ⋃𝑆
𝑆∈𝐹
We say that a subset 𝑆 ∈ 𝐹 covers all elements in X. Our goal is to find a minimum size subset
𝐶 ⊆ 𝐹 whose members cover all of X.
𝑋 = ⋃𝑆
𝑆∈𝐶

CS302
Consider each of the following words as a set of letters: {arid, dash, drain, heard, lost, nose, shun,
slate, snare, thread}. Show which set cover GREEDY-SET-COVER produces, when we break ties
in favor of the word that appears first in the dictionary.

Question 4: 20 Points

Consider following points in 2D


(6,2), (9,5), (-2,2), (-3,4), (-8,8), (-10,4), (-10,3), (-8,-6), (-4,-4), (6,4), (6,-6), (-6,-10), (8,0)
Find the smallest convex set containing all the points using Package Wrap (Jarvis March) and
Graham Scan (Show all iterations).

BEST OF LUCK

CS302
National University of Computer & Emerging Sciences, Karachi
Fall-2020 Department of Computer Science
Assignment 5
Due: 25th December 2020

Max Marks: 60 Points

Question # 1 20 Points

Explain in your own words

(a) What is meant by P and NP Problems? Explain P = NP

P problems

a. (The original definition) Problems that can be solved by deterministic Turing machine
in polynomial-time.
b. (A equivalent definition) Problems that are solvable in polynomial time.

NP problems

c. (The original definition) Problems that can be solved by non-deterministic Turing


machine in polynomial-time.
d. (A equivalent definition) Problems that are verifiable in polynomial time.
i. Given a solution, there is a polynomial-time algorithm to tell if this solution is
correct.

P = NP means whether an NP problem can belong to class P problem. In other words, whether
every problem whose solution can be verified by a computer in polynomial time can also be solved
by a computer in polynomial tim

(b) Why it is important to find approximate solutions for NP Complete Problems


Sol: If a problem is NP-complete, there is very likely no polynomial-time algorithm to find an
optimal solution. The idea of approximation algorithms is to develop polynomial-time
algorithms to find a near optimal solution

(c) What is the difference between NP Complete and NP Hard


NP Problem:
The NP problems set of problems whose solutions are hard to find but easy to verify and
are solved by Non-Deterministic Machine in polynomial time.
NP-Hard Problem:
Any decision problem Pi is called NP-Hard if and only if every problem of NP(say P<subj)
is reducible to Pi in polynomial time.
NP-Complete Problem: Any problem is NP-Complete if it is a part of both NP and NP-
Hard Problem.

CS302
(d) A problem that is solvable in time complexity of 𝑇(𝑛) = 3 ∗ 𝑛𝑛 and space complexity of 𝑆(𝑛) =
𝑛2 and it can be validated in 𝑇(𝑛) = 2𝑛 time. Is it a NP-Complete or NP-Hard? Explain
Sol: NP-Hard as validated in 𝑇(𝑛) = 2𝑛 time.

Question #2

Consider the following APPROX-VERTEX-COVER algorithm. Proof that this algorithm is 2-


approximation method for VERTEX-COVER. 10 Points

APPROX-VERTEX-COVER(G)
C = ∅;
E’=G.E;
while(E’ ≠ ∅ ){
Randomly choose a edge (u,v) in E’, put u and v into C;
Remove all the edges that covered by u or v from E’
}
Return C;

Question 3 10 Points

An Instance (𝑋, 𝐹) of the set-covering problem consists of a finite set X and a family F of subset
of X, such that every element of X belongs to at least one subset of F:
𝑋 = ⋃𝑆
𝑆∈𝐹
We say that a subset 𝑆 ∈ 𝐹 covers all elements in X. Our goal is to find a minimum size subset
𝐶 ⊆ 𝐹 whose members cover all of X.

CS302
𝑋 = ⋃𝑆
𝑆∈𝐶

Consider each of the following words as a set of letters: {arid, dash, drain, heard, lost, nose, shun,
slate, snare, thread}. Show which set cover GREEDY-SET-COVER produces, when we break ties
in favor of the word that appears first in the dictionary

Question 4: 20 Points

Consider following points in 2D


(6,2), (9,5), (-2,2), (-3,4), (-8,8), (-10,4), (-10,3), (-8,-6), (-4,-4), (6,4), (6,-6), (-6,-10), (8,0)
Find the smallest convex set containing all the points using Package Wrap (Jarvis March) and
Graham Scan (Show all iterations)

A) Jarvis March: The points at the hull of convex in ordered form are: (−6, −10) →
(6, −6) → (8,0) → (9,5) → (−8,8) → (−10,4) → (−10,3) → (−8, −6).
B) Graham Scan: The points are as same as the Jarvis March but the deleted points are:
(6,2) → (6,4) → (−2,2) → (−4, −4) → (−3,4). The sorted points are: (−6, −10) →
(6, −6) → (8,0) → (9,5) → (6,2) → (6,4) → (−2,2) → (−4, −4) → (−3,4) →
(−8,8) → (−10,4) → (−10,3) → (−8, −6).

CS302
CS302

You might also like