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
The management of Ventura Inc. approves the purchase of a few computers for the sales team. The management wants only the most b
BaLLatris [955]

Answer:

Ventura Inc requires only System software's

Explanation:

The system software has three major functions which are:

1. File and disk management: this involve managing of files in the system, when user want to save, move, copy, delete and rename files, The system software will handle those task

2. Allocating system resources: The system resources such as time, memory, data input and output are  allocated by the system software. The main memory is managed by the system software to avoid conflict among various task.

3. Monitoring system activities:  The system security and system performance is also monitored by the system software.

The first two functionalities are the requirement of ventura inc  

8 0
3 years ago
The principal objectives of computer security are to prevent unauthorized users from gaining access to resources, to prevent leg
Lena [83]

Answer:

True is the correct Answer for the above question.

Explanation:

  • Computer security is a security in which data of the computer is secured from the access of unauthorized users. It is primarily achieved to stop the access grant to the unauthorized user.
  • It means that there is an authorization point which decides that the user is authorized or not. If the user is authorized then only he can enter the system otherwise he can not able to enter the system.
  • It helps to secure the data and the data is the important point of the computer system.
  • The question also states the same which is described above. Hence true is the correct answer.

3 0
3 years ago
Which RFC reserves three ranges of IP addresses for private use - a single Class A (10.0.0.0-10.255.255.255), 16 Class Bs (172.1
erica [24]

Answer:

The answer is "1918".

Explanation:

The RFC stands for "remote function call", it is also known as an abbreviated form. It is an application, that responses in a technical online design Task Force, it is also known as a document, which was prepared for review by shareholders to collects some information.  

The RFC reverses is also known as an idea, that uses IP version 4 to reverse the IP address, this process is done by TCP/IP protocol, which is defined under RFC 1918.  

4 0
3 years ago
The term used to describe whereby old and new media are available via the integration of personal computers and high speed satel
garri49 [273]

The term used to describe whereby old and new media are available via the integration of personal computers and high speed satellite based phone or cable links is: media convergence.

<h3>What's a good illustration of media convergence? </h3>
  • Smartphones, laptops, and ipads are the finest instances of media convergence since they combine several forms of digital media, including radio, cameras, TVs, music, and more, into a single, straightforward gadget.
  • The blending of formerly separate media platforms and technologies through digitization and computer networking is referred to as media convergence. Another name for this is technical convergence.
  • Media ownership concentration, sometimes referred to as media consolidation or media convergence, is the process through which a smaller number of people or organisations come to control a larger portion of the mainstream media.
  • According to recent study, there is a rising amount of consolidation in the media sectors, which are already highly concentrated and controlled by a very limited number of companies.

To learn more about media convergence, refer to the following link:

brainly.com/question/25784756

#SPJ4

6 0
1 year ago
Beyond personal self-directed learning, engaging the management team of the technology group is a process of strategic learning
ASHA 777 [7]

Answer:

The statement personal self -directed learning is true because, it is a dynamic learning process that can be both change for the organization and contribute to fresh ideas for potential placement of the company.

Explanation:

Solution

In an organisation the management team plays an important role toward's its growth.

This plays a vital role in meeting up to its long-term targets, forging ahead with passion or determination and making any form of adjustments when necessary.

Management is not just about implementing specified proposals. It calls for the analysis of different critical structure, on spot decision-making. this is about learning and can sometimes lead to newly taught results, sometimes positive other times.

Management refers to being actively and consistently engaged with a group of people who work for them. Successful management entails good team work, support from top to bottom of its hierarchy. It requires leadership over a group of individuals who are expected to execute thoughts and opinions on the organisation.

As a part of the management committee also allows for the team leaders to build individual talent. They learn from their way through the various hiccups they face.

Therefore, aside personal self-directed learning, joining the technology group's management team is a proactive learning process that can be both transformative for the organization and contribute to fresh ideas for potential placement of the company.

5 0
3 years ago
Read 2 more answers
Other questions:
  • Search the internet for news of a motor vehicle collision in your community involving drugs or alcohol. Keeping in mind that you
    8·1 answer
  • Security and protection as it relates to operating systems is grouped into four categories: Availability, Data integrity, Authen
    9·1 answer
  • When RadioButton objects are contained in a group box, the user can select only one of the radio buttons on the panel.
    12·1 answer
  • PLEASE VERY IMPORTANT Conduct research on graphic design skills in your area and explore the different courses that they offer l
    12·1 answer
  • If I'm screen sharing and I plug in a HDMI, will it screen share what the HDMI is plugged into, and can you talk at the same tim
    11·1 answer
  • First, read in an input value for variable valCount. Then, read valCount integers from input and output each integer on a newlin
    6·1 answer
  • List any two programs that are required to play multimedia products
    8·1 answer
  • Why do many experts recommand longer time horizonal if you are doing high risk investment
    7·1 answer
  • What is the purpose of quick access toolbar?
    7·1 answer
  • Which cloud technology characteristic ensures that a cloud customer can make changes to her cloud database from her smartphone w
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!