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
Nga, Kai, and Jason volunteer in the school library. They want to find the average number of pages of a library book. It would b
Serga [27]

Answer: Kai

Step-by-step explanation:

I did the assignment and got it correct

4 0
3 years ago
Read 2 more answers
Solve for x. 2/3x−5=21 x = 39 x=52/3 x = 24 x=32/3
Finger [1]

2x/3 - 5 = 21

2x/3 = 26

2x = 78

x = 39

OPTION A is the answer.....

8 0
3 years ago
Read 2 more answers
I need help with 7-14
aliina [53]
7: $200<3x-y(28) where x represents each kids money out of it and y represents the parents pay.
8: 7.00>(is greater then or equal to) 0.75X + 1.29Y where X is the amount of bagels and Y is the amount of cream cheese containers.
9: $25 + $75>4X where X is the shirts
10: 720-120>(greater then or equal to) 32X where X is the number of people in each row
11: 2400= 2100+ X(1/20) where X is the value of all things sold.
12: 2000<(X7)-668 where X is the amount of cans in one day.
13: 100> 7X - 10Y where X equals the amount of months and Y equals the amount of CD's
14: $80 - $22> (greater than or equal to) 17X where x equals the amount of shirts.

first off sorry it took so long to answer, these long word questions are time consuming and i havent done them in a while so i had to refresh my memory, secondly the equations all end where i say the word "where", thirdly i am absolutely sure of all these answers except for the first one, the first one i am pretty sure i still got it but not 100%.

hope this helps.
5 0
3 years ago
Marvin used a customary unit of measure to estimate the weight of a watermelon he grew in his backyard what could the estimated
Andrej [43]

Answer:

Usually pounds (lb) .About an an average of  20 to 25 pounds (lbs)

Step-by-step explanation:

Since Marvin uses Customary units, and considering the Watermelon.

Pounds,  He could estimate based on average of 20 to 25 pounds.

He could choose another customary units, but it wouldn't be practical and unusual to say a watermelon of 160 quarters, also it would leave all the listeners without parameters.

So, definitely pounds.

3 0
3 years ago
PPPPPPPPPPLLLLLLLLLLZZZZZZ HELP!<br><br> A.<br> B.<br> C.<br> D.
BigorU [14]
The answer to the question is d

7 0
3 years ago
Other questions:
  • Jay Miller insured his pizza shop for $200,000 for fire insurance at an annual rate per $100 of $.49. At the end of 10 months, J
    7·1 answer
  • Find each percent of change. 105 is decreased to 32
    9·1 answer
  • What is the area of a circle with a radius of 15 feet. Use 3.14 for pi. Round 2 decimal places
    11·1 answer
  • Circle O has a circumference of approximately 44 in.
    13·2 answers
  • Please help ASAP!Simplify : <br> 3x^3/6<br> And <br> 10x^5/6x^3
    11·1 answer
  • Write a compound inequality to represent all of the numbers between -4 and 6.
    15·1 answer
  • Is -14 greater than less than or equal to -3
    7·1 answer
  • What are the coordinates of point X?<br> (1,3)<br> (3, -1)<br> (3,1)<br> (-1, -3)
    9·2 answers
  • EASY BRAINLIEST PLEASE HELP!!
    14·2 answers
  • Find the H.C.E of 108 and 72.​
    10·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!