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
Klio2033 [76]
3 years ago
12

Your job is to prepare a lineup of n awardees at an award ceremony. You are given a list of m constraints of the form "i wants t

o receive an award before j." If you violate a constraint, it might upset the affected award recipient (i) and then i may leave the ceremony. Give an algorithm that prepares such a lineup, (or says that it is not possible) in O ( m + n ) time.
Mathematics
1 answer:
DanielleElmas [232]3 years ago
6 0

Answer:

The idea is to use the concept of topological sorting.

Complexity of this algorithm is equal to complexity of DFS algorithm, that is, O(m+n).

Step-by-step explanation:

The idea is to use the concept of topological sorting.

A topological sort also called a topological ordering of a directed graph is a linear ordering of its vertices in a way that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

A topological sorting is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

For every edge (U - - >V), create a directed edge from U to V.

While creating an edge, if an edge creates a cycle, then it is not possible.

n= number of awardees

m= the number of constraint

Let n represent the vertices of a graph and constraints m is representing edges of a graph.

and graph is represented in adjacent of O(m+n)

Constraint i wants to receive award before j

Graphical representation - - - - - > (i) - - - - - - > (j) j depends on i

1. Presently run topological olding on graph G(n, m) where n is vertices and m is edges.

2. Run DFs on Graph, a temporary stack

3. Firstly call topological sorting for all its adjacent vertices and then push it to a stack. Finally, print content of stack.

4. Vertex is push to stack only when all adjacent vertices are already in stack.

Complexity of this algorithm is equal to complexity of DFS algorithm, that is, O(m+n).

You might be interested in
Suppose you invest $63 a month in an annuity that earns a 3.3% APR
lisov135 [29]

Answer: $3227.93 APEX

4 0
3 years ago
A) Find the distance of line segment PR. Round answer to the nearest tenth. B) Find the distance around the park (perimeter).
juin [17]

Answer:

A. PR = 80.6 yd

B. Perimeter = 190.6 yd

Step-by-step explanation:

A. Distance between P(10, 50) and R(80, 10):

PR = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

PR = \sqrt{(80 - 10)^2 + (10 - 50)^2}

PR = \sqrt{(70)^2 + (-40)^2}

PR = \sqrt{4,900 + 1,600}

PR = \sqrt{6,500}

PR = 80.6 yd (nearest tenth)

B. Distance around the park = Perimeter = PR + PQ + QR

PR = 80.6 yd

PQ = |50 - 10| = 40 yd

QR = |80 - 10| = 70 yd

Perimeter = 80.6 + 40 + 70

Perimeter = 190.6 yd

7 0
3 years ago
Sergio is S years old. Which expression shows how old will he be 7 years from now?
aniked [119]
The answer is C.

If Sergio is 'S' years old, and you want to know how old he'll be in 7 years, add 7 years to his age.

So: s + 7

Hope this helps!
3 0
3 years ago
Read 2 more answers
a homeowner wants to carpet 2 rooms that each measure 12 feet by 15 feet. how many square yards of carpet should be ordered?
amm1812
12 x 15 = 180

180 x 2 = 360

360 square yards of carpet should be ordered.
4 0
3 years ago
According to the Department of Transportation, 27% of domestic flights were delayed in the last year at JFK airport. Five flight
Mars2501 [29]

Answer:

The probability that all the five flights are delayed is 0.2073.

Step-by-step explanation:

Let <em>X</em> = number of domestic flights delayed at JFK airport.

The probability of a domestic flight being delayed at the JFK airport is, P (X) = <em>p</em> = 0.27.

A random sample of <em>n</em> = 5 flights are selected at JFK airport.

The random variable <em>X</em> follows a Binomial distribution with parameters <em>n</em> and <em>p</em>.

The probability mass function of <em>X</em> is:

P(X=x)={5\choose x}0.27^{x}(1-0.27)^{5-x};\ x=0,1,2...

Compute the probability that all the five flights are delayed as follows:

P(X=5)={5\choose 5}0.27^{5}(1-0.27)^{5-5}=1\times 1\times 0.207307=0.2073

Thus, the probability that all the five flights are delayed is 0.2073.

4 0
3 years ago
Other questions:
  • Which relations are functions? Select function or not a function for each graph
    12·1 answer
  • Use triangles to find the sum of the interior angle measures of the polygon. What's the answer?
    10·2 answers
  • Find the y and x axis of 3 and -5
    15·1 answer
  • What is the value of st divided by (6r) if r =5 and t =45
    7·1 answer
  • cleaning diesel dispensers for 35 mins you have completed 6 how many mins has it taken you to clean 1
    12·1 answer
  • What is the surface area of this prism?
    7·1 answer
  • PLEASE HELP, WILL GIVE BRAINLIEST FOR RIGHT ANSWER!
    14·2 answers
  • I need a word problem for this system of equation y=-80x+300. and I also need to explain the initial value and discuss the rate
    9·1 answer
  • Solve the system of equations by substitution <br><br> y = 2x + 1 and 3x + y = 16
    8·1 answer
  • Maxine and her daughter are going grocery showing after she gets off work. Maxine sees that apples are $0.25, while bananas are
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!