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
_____ are unique identifiers of computer or network addresses on the internet.
Gnesinka [82]
The answer is IP address.
5 0
3 years ago
Read 2 more answers
A _____ model is one that is automatically adjusted based on changing relationships among variables.
BabaBlast [244]

Answer: dynamically modified model

Explanation:

7 0
1 year ago
LILLE VIC LUNCUL ANCI.
tatiyna

The correct option is C. toward the floor.

The magnetic force on the moving negative charge acts towards the floor.

<u>Explanation</u>:

The direction of the force applied on the moving charged particle placed in the magnetic field can be determined with the help of Fleming’s Left hand rule.

The current flows in the direction opposite to the direction of electron. If the electron moves from negative terminal to positive terminal, then the current will flow from positive terminal to negative terminal.

As given, the direction of electron- South to North

So the direction of current will be- North to South

Using Fleming's Left hand rule we get the direction of force in downward direction, i.e. towards the floor.

5 0
3 years ago
. Pam is showing her audience, live on the internet, an article that was posted to a reputable website just hours before her spe
Afina-wow [57]

Answer:

webidence

Explanation:

Webidence is a web source or web sources displayed as evidence during a speech, found by using real-time web access or webpage capture software.

This is an online material which serve as a form of evidence to support ones speech or presentation.

It can be gathered or gotten by making use of capture software, real time web access or webpage.

The main idea behind it is to authenticate your presentation.

4 0
3 years ago
Microsoft word 365 allows cells to be split into how many columns
Bogdan [553]

Answer:

Microsoft word 365 allows two columns

8 0
3 years ago
Read 2 more answers
Other questions:
  • I WILL GIVE BRAINLIEST TO WHO ANSWERS FIRST AND CORRECTLY.
    5·1 answer
  • Which button would you use to quickly add addresses to a mail merge envelope?
    5·1 answer
  • What are personal skills? A manner of individual style How a person manages and expresses oneself One's ability to excel at spor
    13·2 answers
  • A model release can be either oral or written down. true or false
    11·2 answers
  • The steps for creating a newsletter are to ____.
    10·1 answer
  • _______ view focuses on the text and content of a document, without much information on the page layout.
    7·1 answer
  • Differences between electromechanical era and electronic era in point.<br>PLZ HELP​
    6·1 answer
  • State why hexadecimal is used to display the error code
    11·1 answer
  • What is an example of a hard skill?
    12·2 answers
  • WHO WANT P O I N T S.................................................
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!