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
Type dig www.example A in order to get the IP address of www.example. What’s the TTL of the A record returned in the response? W
fiasKO [112]

Answer:

Your computer now has the IP address of that website cached, and no longer has to lookup the IP address of that domain name. The TTL of the first query is bigger than the TTL of the second query as less time was taken to execute the request.

Explanation:

On the first request to the website, the computer needs to contact other machines to find the record of the IP address.

On the second request, the computer already has the IP address and can use that to connect.

6 0
3 years ago
Select the correct answer from each drop-down menu.
Lelu [443]

Answer:

First: .Net

Second: New Zealand

Explanation:

Net is short for Network.

NZ means New Zealand.

3 0
3 years ago
Read 2 more answers
When did internet came to existence?
Luden [163]
1982 the Internet protocol was introduced as the standard network protocol on the ARPANET.

1981 access to the ARPANET was expanded.
7 0
3 years ago
1. As part of your community, your school, and your neighbourhood, how else does ICT have an impact on social
NeX [460]

Answer:

helthcare systems, aviation, entertainment, retail, etc

Explanation:

ICT has made life easy, it has made an interconection accross the world. in the helthcare system, ICT has created a positive impact because now a days body check up is been made through computers.

in the aviation, we use computers to control the the traffic of airplanes.

5 0
3 years ago
Write a short-essay discussing your own stand on social media usage for students.​
hjlf

Answer:

More than half of the world’s population uses the internet. This is highlighted by social media users increasing by 21% since 2015, with 2.8 billion users reported globally in 2017.

Humans are social animals. We always like to remain in some group or another, and we prefer to follow what this group does. All of our traditions and cultures are the product of <em><u>this</u></em> group-oriented facet of human nature.Everyone is connected to one another in this vast network generated by the Internet.It illuminates the lives of thousands of people by spreading knowledge internationally, thereby making us global citizens. 

<h2><em><u>NOT</u></em><em><u> </u></em><em><u>COPIED</u></em><em><u> </u></em><em><u>ANSWER</u></em><em><u> </u></em></h2>
3 0
3 years ago
Other questions:
  • _____ provide the standards, syntax, statements, and instructions for writing computer software
    14·1 answer
  • You can choose which rules you want excel to use by enabling and disabling them in the ____ area in the excel options dialog box
    11·1 answer
  • The first screen you see when you open word2016 what is called?​
    5·2 answers
  • Which of the following statements is true?
    8·1 answer
  • Implement the RC4 stream cipher in C++. User should be able to enter any key that is 5 bytes to 32 bytes long. Be sure to discar
    7·1 answer
  • 5. Which of the following views is used to run a PowerPoint presentation?
    11·2 answers
  • Remember partially filled arrays where the number of elements stored in the array can be less than its capacity (the maximum num
    14·1 answer
  • Any correct answers will be helpful.
    13·1 answer
  • Which of the following is considered true regarding modern work environments?
    9·1 answer
  • In cell b12 create a formula using max f7nction to calculate maximum value in B4:B9
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!