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
On what dates did the 2016 Olympics take place( list all)
kow [346]
Hi!

The 2016 Olympics took place from August 5th, 2016 - August 21st, 2016.
3 0
3 years ago
Read 2 more answers
Software that instructs the computer how to run applications and controls the display/keyboard is known as the
saw5 [17]
Answer is : operating system
8 0
3 years ago
Why did the boy run from the pillow...... wrong answers only
Savatey [412]

He thinks there is a demon hiding innit thus, he runs and calls his mom. His mom says "Jimmy there's nothing in that pilow young man!" Jimmy walks back to his room scared if its still there. He hops into bed hoping that he can get a good nights rest. The next day, Jimmy asks if he can go buy another pillow. His mom says "As long as it makes you feel safe then ok." Young Jimmy, jumping in excitement, goes to the checkout zone to buy his new pillow. When they get home, Jimmy and his mom eat dinner and then head for bed. Jimmy hops into bed and knows that everything will be ok. The end.

4 0
3 years ago
Write a function named times_ten. the function should accept an argument and display the product of its argument multiplied time
viva [34]
Since you did not specify a language  i am assuming C

void  x10(int   n){
printf("%d \n",n*10);
return;
}

3 0
3 years ago
What does a spam e-mail normally promise you?
nlexa [21]
The answer is a virus
7 0
3 years ago
Other questions:
  • Write a program to add two number marie simulator.
    15·1 answer
  • When you arrive at work one morning, your inbox is full of messages complaining of a network slowdown. you collect a capture fro
    12·1 answer
  • What is the maximum upload speed you can get on an isdl internet connection?
    9·1 answer
  • Evie clicks through her presentation slides and realizes they all have transition effects coming from the same location, from th
    13·1 answer
  • 9. Which of the following is the<br>leading use of computer?​
    13·1 answer
  • You wrote a program to allow to guess a number chosen randomly.
    10·2 answers
  • Pleaseeeeeeeee I will give a brainliest
    7·1 answer
  • The Curtis Publishing Company's early marketing research efforts mainly had to do with _____. people who drove automobiles peopl
    10·1 answer
  • What types of things were often NOT captured in early photographs?
    7·1 answer
  • What are common considerations businesses need to make before purchasing new computers? Check all of the boxes that apply.
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!