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
Which of the following are incident priorities?
xenn [34]

Answer:

what are the options?

reply in comment so i can help:)

5 0
3 years ago
The transport layer protocol used by the tcp / ip suite that does not provide guarantees on ordering or confirmation of receipt
VARVARA [1.3K]
UDP = connectionless vs. TCP is connection oriented.
4 0
3 years ago
Which of the following represent features of free software licensing? Check all of the boxes that apply.
Iteru [2.4K]

Answer: A :is concerned with defending users’ freedom of use

C:makes source code available for editing

Explanation:

7 0
3 years ago
What term is used to describe a list of security policies that is associated with an object?
Artemon [7]

Answer:

An Access control list (ACL) is used to describe a list of security policies that is associated with an object

5 0
3 years ago
Write a program that replaces words in a sentence. The input begins with an integer indicating the number of word replacement pa
kramer

Answer: provided in the explanation segment

Explanation:

This is the code to run the program:

CODE:  

//Input: 3 automobile car manufacturer maker children kids

  //15 The automobile manufacturer recommends car seats for children if the automobile doesn't already have one.

  import java.util.Scanner;

  public class LabProgram{

  public static int findWordInWordList(String[] wordList, String wordToFind, int numInList) {

          for (int i = 0; i < numInList; i++) {

              if (wordList[i].equals(wordToFind)) {

                  return i;

              }

          }

          return -1;

      }

      public static void main(String[] args) {

          Scanner scan = new Scanner(System.in);

          String[] original_String = new String[20];

              String[] modified_String = new String[20];

          int numInList = scan.nextInt();

          for (int i = 0; i < numInList; i++) {

              original_String[i] = scan.next();

              modified_String[i] = scan.next();

          }

          int num_Of_Words = scan.nextInt();

          String[] words_To_Replace = new String[num_Of_Words];

          for (int i = 0; i < num_Of_Words; i++) {

              words_To_Replace[i] = scan.next();

          }

          int indx;

          for (int i = 0; i < num_Of_Words; i++) {

              indx = findWordInWordList(original_String, words_To_Replace[i], numInList);

              if (indx != -1)

                  words_To_Replace[i] = modified_String[indx];

          }

          for (int i = 0; i < num_Of_Words; i++)

              System.out.print(words_To_Replace[i] + " ");

          System.out.println();

      scan.close();

      }

  }

cheers i hope this helps!!!!1

3 0
3 years ago
Other questions:
  • Productivity software has been used for a number of years. Recent advancements in productivity software technology have made ___
    14·1 answer
  • If an ARQ algorithm is running over a 40-km point-to-point fiber optic link then:
    12·1 answer
  • Which strategy are you using when you only read the title, section headings, and captions?
    12·2 answers
  • Public static String doSomething(String s) { final String BLANK = " "; //BLANK contains a single space String str = ""; //empty
    6·1 answer
  • The physical elements needed for the production of digital media, such as computers, servers, and so on are called the {Blank}
    8·1 answer
  • You will implement three different types of FFs with two different reset types. You have to show your results on your FPGA. You
    9·1 answer
  • Send me the answers<br>​
    15·1 answer
  • ................. are used to summarize data (option) (a) report (b) action ​
    12·2 answers
  • Convert the following denary numbers into binary using 8-bit register:
    6·1 answer
  • Which of the following tabs on the Ribbon contains the commands for adding tables, pictures and shapes into a publication? Quest
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!