Classified in Computers

Written at on English with a size of 3.68 KB.

7- Set Cover to Efficient Recruiting
input: set U of elements, collection S1, . . . , Sm of subsets of U, integer k ≥ 0
.Construct an instance of the Efficient Recruitment Problem where the sports are U, the applicants are {1, . . . , m} and where for every s ∈ U and 1 ≤ i ≤ m, M[s, i] = 'qualified' if s € Si and 'no qualified' otherwise.
.Call the oracle for Efficient Recruiting with input M and k
.Return the result (yes or no) of the previous call

8- Consider graph G = (V, E);
. U = V(G);
. S_i = {u, v}; // where (u, v) is an edge of G.
. If C is a vertex cover for G of size k ⇒ by definition then, for every edge (u, v) in G either u ∈ C or v ∈ C. C is solution for Hitting Set because it must intersect every set Si
.Now suppose H is a hitting set of U of size k. Since H intersects every set, it has at least one endpoint of every edge. Set C to be H.
** Verifier for Exam Scheduling Problem
- lists l1, . . . , ln,
- lists a_11, . . . , a_10 where each list a_i is a subset of {1, . . . , n} {a_i encodes the courses whose exam is scheduled in day i}
.Check that every course is scheduled in exactly one day and that every pair of courses scheduled in the same day do not have any student in common **
9 - input: a graph G
.Pick any arbitrary node v from G
for each node u adjacent to v do
.Construct a new graph H in the following way: Initially, place in H all nodes and edges in G. Furthermore, we add to H two new nodes, that we call u' and v', and the new edges (u', u) and (v',v)
.Call the oracle for Hamiltonian Path with input H.
.If the result of the previous call is yes then
stop and return yes
.end if
.End for
retur n no
Let Y be a NP-complete. We have mentioned in class that Y belongs to P if and only if P=NP. In this exercise we ask you to prove it.
(a) If Y belongs to P then P=NP. Assume that Y belongs to P. Let X be any problem in NP.  Since Y is NP-complete it follows that X (

)>)>
(b) If P=NP then Y belongs to P. This is immediate. Assume that P=NP. Since Y belongs to NP and P=NP then Y belongs to P as well
Algorithm LIS
1: input: A sequence A[1], . . . , A[n] of integer numbers
2: for j := 1 to n do
3:    M[j] := 0
4:    for i := 1 to j − 1 do
5:       if A[i] < a[j]="" then="">
6:          M[j] := max(M[j], M[i])
7:       end if
8:     end for
9:     M[j] := M[j] + 1.
10: end for
11: {Finally, it is only necessary to find the maximum value in M}
12: maximum := 0
13: for j := 1 to n do
14:     maximum := max(maximum, M[j])
15: end for
16: return maximum