1answer.
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
AysviL [449]
3 years ago
14

There are n poor college students who are renting two houses. For every pair of students pi and pj , the function d(pi , pj ) ou

tputs an integer between 1 and n 2 that indicates the amount of drama that will ensue if both students are placed in the same house. The total drama is maxi,j d(pi , pj ) over all pairs of students in the same house. That is, drama is not cumulative: it is determined by the worst pair of people.
Required:
Given an integer k as input, design an O (n2) algorithm to determine how you can partition the students such that the total drama < k, or assert that no solution exists.
Computers and Technology
1 answer:
Nuetrik [128]3 years ago
3 0

Answer:

Here the given problem is modeled as a Graph problem.

Explanation:

Input:-  n, k and the function d(pi,pj) which outputs an integer between 1 and n2

Algorithm:-We model each student as a node. So, there would be n nodes. We make a foothold between two nodes u and v (where u and v denote the scholars pu and pv respectively) iff d(pu,pv) > k. Now, Let's call the graph G(V, E) where V is that the vertex set of the graph ( total vertices = n which is that the number of students), and E is that the edge set of the graph ( where two nodes have edges between them if and only the drama between them is bigger than k).

We now need to partition the nodes of the graph into two sets S1 and S2 such each node belongs to precisely one set and there's no edge between the nodes within the same set (if there's a foothold between any two nodes within the same set then meaning that the drama between them exceeds k which isn't allowed). S1 and S2 correspond to the partition of scholars into two buses.

The above formulation is akin to finding out if the graph G(V,E) is a bipartite graph. If the Graph G(V, E) is bipartite then we have a partition of the students into sets such that the total drama <= k else such a partition doesn't exist.

Now, finding whether a graph is bipartite or not is often found using BFS (Breadth First algorithm) in O(V+E) time. Since V = n and E = O(n2) , the worst-case time complexity of the BFS algorithm is O(n2). The pseudo-code is given as

PseudoCode:

// Input = n,k and a function d(pi,pj)

// Edges of a graph are represented as an adjacency list

1. Make V as a vertex set of n nodes.

2. for each vertex  u ∈ V

\rightarrow  for each vertex v ∈ V

\rightarrow\rightarrowif( d(pu, pj) > k )

\rightarrow\rightarrow\rightarrow add vertex u to Adj[v]   // Adj[v] represents adjacency list of v

\rightarrow\rightarrow\rightarrow add vertex v to Adj[u] // Adj[u] represents adjacency list of u

3.  bool visited[n] // visited[i] = true if the vertex i has been visited during BFS else false

4. for each vertex u ∈ V

\rightarrowvisited[u] = false

5. color[n] // color[i] is binary number used for 2-coloring the graph  

6. for each vertex u ∈ V  

\rightarrow if ( visited[u] == false)

\rightarrow\rightarrow color[u] = 0;

\rightarrow\rightarrow isbipartite = BFS(G,u,color,visited)  // if the vertices reachable from u form a bipartite graph, it returns true

\rightarrow\rightarrow if (isbipartite == false)

\rightarrow\rightarrow\rightarrow print " No solution exists "

\rightarrow\rightarrow\rightarrow exit(0)

7.  for each vertex u ∈V

\rightarrow if (color[u] == 0 )

\rightarrow\rightarrow print " Student u is assigned Bus 1"

\rightarrowelse

\rightarrow\rightarrow print " Student v is assigned Bus 2"

BFS(G,s,color,visited)  

1. color[s] = 0

2. visited[s] = true

3. Q = Ф // Q is a priority Queue

4. Q.push(s)

5. while Q != Ф {

\rightarrow u = Q.pop()

\rightarrow for each vertex v ∈ Adj[u]

\rightarrow\rightarrow if (visited[v] == false)

\rightarrow\rightarrow\rightarrow color[v] = (color[u] + 1) % 2

\rightarrow\rightarrow\rightarrow visited[v] = true

\rightarrow\rightarrow\rightarrow Q.push(v)

\rightarrow\rightarrow else

\rightarrow\rightarrow\rightarrow if (color[u] == color[v])

\rightarrow\rightarrow\rightarrow\rightarrow return false // vertex u and v had been assigned the same color so the graph is not bipartite

}

6. return true

You might be interested in
Assume that ip has been declared to be a pointer to int and that result has been declared to be an array of 100 elements . Assum
Bogdan [553]

Answer:

The expression of this question can be given as:

Expression:

*ip + 1

Explanation:

In this question, it is given that ip variable has been declared and initialized and the ip variable is in the first half of the array. It finds the expression whose value is after the element of the array that ip points. So the expression to this question is *ip + 1. Where * is used to define ip variable as a pointer and its value is increased by 1 that is given in the question.

7 0
3 years ago
Fryshta is using the Help window in PowerPoint to learn about inserting Smart Shapes into a presentation. She currently has a He
Rainbow [258]

Answer: Pin

Explanation:

Pin button is the button that is used for sticking or saving the ideas from the windows or web on that very place.This feature helps in reviewing or getting the idea back later anytime from the window as per users need. User use this button for saving any food recipe, steps of any process, guidelines etc.

  • According to the question, Fryshta can use pin button from the help window for sticking or pinning the steps of inserting shapes in her presentation.She can have a look at the steps whenever she want.
8 0
3 years ago
Write a program that calculates the occupancy rate for ahotel. The program should start by asking the user how many floorsthe ho
Oksana_A [137]

Answer:

Here is the C++ program:

#include <iostream>  //to use input output functions

using namespace std;   //to identify objects like cin cout

int main(){  //start of main function

       int MinFloors = 1;  //minimum number of floors

       int MinRooms  = 10; //minimum number of rooms

       int NoOfFloors;  //stores number of floors

       int NoOfRooms;  //stores number of rooms

       int OccupiedRooms;  //stores number of rooms occupied

       double TotalRooms=0, TotalOccupied=0;   //stores computed total number of rooms and total number of occupied rooms

       cout<<"How many floors does the hotel have? ";  //prompts user to enter number of floors

       do{  //iterates until the user enters valid number of floors

           cout<<"(cannot be less than "<<MinFloors<<"): ";  //error message

           cin >>NoOfFloors;  //reads number of floors from user

       }while(NoOfFloors<MinFloors);  //repeats as long as number of floors is less than minimum number of floors

       for(int floor=1; floor <= NoOfFloors; floor++){    //iterates through the floors to skip third iteration

           if(floor == 3){   //if floor is third floor

               continue;             }  

           cout<<"How many rooms are on floor " <<floor;  //prompts user to enter number of floors

           do{  //start of do while loop

               cout<<"(cannot be less than "<<MinRooms<<"): ";  //error message

               cin >>NoOfRooms;  //reads number of rooms from user

           }while(NoOfRooms<MinRooms);    //iterates as long as number of rooms are less than valid minimum number of rooms

           TotalRooms += NoOfRooms;   //adds number of rooms to the count of total number of rooms

           cout<<"How many of those rooms are occupied?";  //prompts user to enter number of rooms occupied

           do{  //start of do while loop

         cout<<"(cannot be less than 0 or greater than "<<NoOfRooms<<"): ";  //generates error message

         cin >>OccupiedRooms;  //reads number of rooms occupied by user

           }while(OccupiedRooms<0 || OccupiedRooms>NoOfRooms);   //iterates as long as the number of occupied rooms are less than 0 or greater than number of rooms

           TotalOccupied += OccupiedRooms;    }    //adds number of rooms occupied to the count of total number of occupied rooms    

       cout<<"\nThe hotel has a total of "<<TotalRooms<<" rooms"<<endl;  //displays the total number of rooms in the hotel

       cout<<TotalOccupied<<" are occupied."<<endl;  //displays the total number of occupied rooms

       cout<<(TotalRooms-TotalOccupied)<<" are unoccupied."<<endl;  //displays the total number of unoccupied rooms

cout<<"The occupancy rate is: "<<100*(TotalOccupied/TotalRooms)<<"%"<<endl;     }  //computes and displays the occupancy rate

   

Explanation:

The program first prompts the user to enter number of floors in the hotel. Lets say user enters 6. This is stored in NoOfFloors So

NoOfFloors = 6

So the loop runs for 6 times

Next it asks user to enter the number of rooms in the floor 1. Lets say user enters 12 so this is stored in NoOfRooms so

NoOfRooms = 12

TotalRooms += NoOfRooms;

this statement keeps adding number of rooms to TotalRooms so

TotalRooms = 12

Next program asks user about the number of occupied rooms. Lets say user enters 10 so this is stored in OccupiedRooms so

OccupiedRooms = 10

this statement keeps adding number of rooms to TotalOccupied so

 TotalOccupied += OccupiedRooms;

TotalOccupied = 10

At next iteration program asks user again to enter number of rooms in floor 2. Suppose user enters 14 so

NoOfRooms = 12

TotalRooms += NoOfRooms;

TotalRooms = 12+14

TotalRooms = 26

Program asks again to enter number of occupied rooms so it becomes:

OccupiedRooms = 8

this statement keeps adding number of rooms to TotalOccupied so

 TotalOccupied += OccupiedRooms;

TotalOccupied = 10+8

TotalOccupied = 18

Next is skips floor 3 and iteration 3. and asks user to enter number of rooms in floor 4. Suppose user enters 14

Number of rooms become:

TotalRooms = 12+14+14

TotalRooms = 40

and suppose user enters 14 as occupied rooms so total occupied become:

TotalOccupied = 10+8 + 14

TotalOccupied = 32

For floor 5: Suppose user enters 13

TotalRooms = 12+14+14+13

TotalRooms = 53

For floor 5: Suppose user enters 10

TotalOccupied = 10+8 + 14+10

TotalOccupied = 42

For floor 6: Suppose user enters 12

TotalRooms = 12+14+14+13+12

TotalRooms = 65

For floor 6: Suppose user enters 11

TotalOccupied = 10+8 + 14+10+11

TotalOccupied = 53

Now the loop breaks

Hence

TotalRooms = 65

TotalOccupied  = 53

total unoccupied = TotalRooms-TotalOccupied = 65-53 = 12

The occupancy rate is: 100*(TotalOccupied/TotalRooms) = 100*(53/65) = 81.5385

The output of the program is attached in a screenshot.

6 0
3 years ago
The endocrine system is composed of many parts of the body.<br> a)True<br> b)False
Finger [1]
It is a) true because its compouse by organs and body tissues
4 0
3 years ago
Read 2 more answers
When the wires are connected to the terminals of the battery, what causes electric current in the circuit?
Anastaziya [24]

Answer: The battery provides a voltage between terminals. The electric field set up in a wire connected to the battery terminals causes the current to flow, which occurs when the current has a complete conducting path from one terminal of the batter to the other. This is called a circuit.

Explanation:

4 0
3 years ago
Other questions:
  • You use a ____ following the closing brace of an array initialization list.
    12·2 answers
  • Your grandmother was an established artist and left you several original paintings after she died. Which of these statements is
    6·1 answer
  • What are the three types of programming design?
    15·1 answer
  • Which turn best describe news one is connected to the government and is used as a political tool more than as a business product
    12·1 answer
  • For the description below, develop an E-R diagram:
    9·1 answer
  • a pair of shoes is on sale for 15% off with this discount customers will pay $9 if they buy the shoes ​
    14·1 answer
  • Will give brainliest!!!!!!!!
    15·2 answers
  • Drag each tile to the correct box.
    8·1 answer
  • Describe your ideas for a keyboarding game that would help someone improve their skills.
    6·1 answer
  • In cyber security, one of the best ways to protect a computer or network is with a strategy called defense in depth. This strate
    10·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!