answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
PolarNik [594]
1 year ago
12

Consider a set A = {a1, . . . , an} and a collection B1, B2, . . . , Bm of subsets of A (i.e., Bi ⊆ A for each i). We say that a

set H ⊆ A is a hitting set for the collection B1, B2, . . . , Bm if H contains at least one element from each Bi – that is, if H ∩ Bi is not empty for each i (so H "hits" all the sets of Bi). We define the Hitting Set Problem as follows. We are given a set A = {a1, . . . , an}, a collection B1, B2, . . . , Bm of subsets of A, and an non-negative integer k. We are asked: is there a hitting set H ⊆ A for B1, B2, . . . , Bm so that the size of H is at most k? Prove that the Hitting Set problem is NP-complete
Computers and Technology
1 answer:
Marizza181 [45]1 year ago
3 0

Answer:

Explanation:

This is actually quite straight forward to solve, first lets be mindful of the explanation so with this basis we can tackle future problems.

The solution may very well may be appeared in the accompanying manner:

This solution needs to display that the set H-one can without much of a stretch confirm in polynomial-time if H is of size k and meets every one of the sets B1.....Bm .

We lessen from Vertex Cover.Consider an example of the Vertex-Cover issue chart G=(V,E) and a positive whole number k.We map it to an occurrence of the hitting set issue as follows.The set An is of vertices V.

Also we know that For each edge e has a place with E we have a set Se Consisting of two end-purposes of e.It is anything but difficult to see that a lot of vertices S is a vertex front of G iff the relating components from a hitting set in the hitting set case.

You might be interested in
Write the definition of a function printAttitude, which has an int parameter and returns nothing. The function prints a message
Oksana_A [137]

Answer:

The function definition, in cpp, for the function printAttitude is given below.

void printAttitude(int n)

{

switch(n)

{

case 1: cout<<"disagree"<<endl; break;

case 2: cout<<"no opinion"<<endl; break;

case 3: cout<<"agree"<<endl; break;

default: break;

}

}

Explanation:

As seen, the method takes an integer parameter.

The method does not returns any value hence, return type is void.

The message is displayed to the console using switch statement which executes on the integer parameter, n.

The values for which output needs to be displayed are taken in cases.

The values for which no output needs to be displayed, is taken in default case.

Every case ends with break statement so that the program execution can be terminated.

This method can be used inside a program as shown.  

PROGRAM

#include <iostream>

using namespace std;

void printAttitude(int n)

{

switch(n)

{

case 1: cout<<"disagree"<<endl; break;

case 2: cout<<"no opinion"<<endl; break;

case 3: cout<<"agree"<<endl; break;

default: break;

}

}

int main() {

// variables to hold respective value

int n;

// user input taken for n

cout<<"Enter any number: ";

cin>>n;

// calling the function taking integer parameter  

printAttitude(n);

return 0;

}

OUTPUT

Enter any number: 11

1. The user input is taken for the integer parameter.

2. Inside main(), the method, printAttitude(), is then called and the user input is passed as a parameter.

3. Since the user entered value is 11 which does not satisfies any of the values in the cases, the default case is entered which does nothing and executes the break statement.

4. Hence, the program displays nothing for the value of 11.

5. When the user enters value 3, the case statement is executed since 3 satisfies one of the case values.

6. The program output for the user input of 3 is as shown below.

OUTPUT

Enter any number: 3

agree

The program ends with return statement.

4 0
1 year ago
5.6 Look carefully at how messages and mailboxes are represented in the email system that you use. Model the object classes that
Annette [7]

Answer:

See explaination for the details of the answer.

Explanation:

A class is a structured diagram that describes the structure of the system.

It consists of class name, attributes, methods and responsibilities.

A mailbox and an email message has some certain attributes such as, compose, reply, draft, inbox, etc.

See attachment for the Model object classes that might be used in the system implementation to represent a mailbox and an email message.

5 0
2 years ago
Define and test a function myRange. This function should behave like Python’s standard range function, with the required and opt
Cerrena [4.2K]

Answer:

Study Python’s help on range to determine the names, positions, and what to do with your function’s parameters.

Use a default value of None for the two optional parameters. If these parameters both equal None, then the function has been called with just the stop value. If just the third parameter equals None, then the function has been called with a start value as well. Thus, the first part of the function’s code establishes what the values of the parameters are or should be. The rest of the code uses those values to build a list by counting up or down.

6 0
1 year ago
Read 2 more answers
Marissa works at a company that makes perfume. She noticed many samples of the perfume were not passing inspection. She conducte
garik1379 [7]
Writing a business letter as if she gets her point across to the head of department then he could change the way they made the perfume so they would pass inspection and standard.
6 0
2 years ago
Read 2 more answers
Children may be placed in restraining devices such as high chairs, swings or bouncy seats
Ratling [72]
Yes in my opinion. People will say no but there is no right answer
8 0
1 year ago
Other questions:
  • Replace the underlines with the words in parentheses that follow: the ____ solves the ____ of a ____ by expressing an ____ in a
    8·1 answer
  • An online game is played with two dice. In this context, explain what is meant by decomposition in a simple way.
    15·1 answer
  • You are researching RAM for a computer you are building for a friend who will be using the system as a home office server for he
    14·1 answer
  • Write a statement to add the key Tesla with value USA to car_makers. Modify the car maker of Fiat to Italy. Sample output for th
    9·1 answer
  • Information gathered from observing a plant grow 3 cm over a two-week period results in _______.a. inferences. b. variables. c.
    11·1 answer
  • Write a Python function called simulate_observations. It should take no arguments, and it should return an array of 7 numbers. E
    7·1 answer
  • In a real-world environment, changing granularity requirements might dictate changes in primary key selection, and those changes
    15·1 answer
  • #Write a function called string_finder. string_finder should #take two parameters: a target string and a search string. #The fun
    14·1 answer
  • Which of these are characteristics of a Python data type? Check all that apply.
    11·1 answer
  • Match the following technologies with their applications.
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!