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
PLEASE HELP What is the y intercept of this line?
Natasha_Volkova [10]

Answer:

I'm pretty positive its (0, 0)

8 0
3 years ago
Read 2 more answers
A potential employer offers to pay you a starting salary of $55,000 a year, and guarantees a
balandron [24]

Answer:270,000

Step-by-step explanation:

i think

6 0
3 years ago
If the area of a park is exactly halfway between 2.4 and 2.5 acres, what is the area of the park? Explain. Please if you know th
grandymaker [24]
"If the area of a park is exactly halfway between 2.4 and 2.5 acres, what is the area of the park" its 2.45 acres.
8 0
3 years ago
A movie theater sends out a coupon for ​65% off the price of a ticket. Write an equation for the​ situation, where y is the pric
damaskus [11]

Answer:150

Step-by-step explanation:

7 0
2 years ago
Consider the formula Distance = speed*time or D = st. Suppose you work 20 miles from your home.
Yuki888 [10]

The time taken to get to work from home with a speed of 30mph will be 40 minutes, 40mph in 30 minutes, and 50mph in 24 minutes.

<h3>What is velocity?</h3>

Velocity is the rate of distance covered per time. Velocity could be average or instantaneous.

Average velocity can be given as;

Average velocity = total distance / total time taken

Units of velocity are given by ⇒ meter/second

As per the given,

Time = distance/speed

Distance = 20 miles

With a speed of 30 mph

Time = 20/30 = 2/3 hour or 40 minutes

With a speed of 40 mph

Time = 20/40 = 1/2 hour or 30 minutes

With a speed of 50 mph

Time = 20/50 = 2/5 hour or 24 minutes

Hence "The time taken to get to work from home with a speed of 30mph will be 40 minutes, 40mph in 30 minutes, and 50mph in 24 minutes".

To learn more about velocity,

brainly.com/question/18084516

#SPJ1

3 0
1 year ago
Other questions:
  • Click an item in the list or group of pictures at the bottom of the problem and, holding the button down, drag it into the corre
    5·2 answers
  • A copy machine makes 36 copies per minute. How many does it make in 3 minutes and 15 seconds
    12·2 answers
  • Jan wants to buy maps for her trip.The map cost 2$ each and she has 25$.Write an equation to represent the amount she has left
    7·2 answers
  • Which complex number has an absolute value of 5?
    10·2 answers
  • 20 cm<br> 16 cm<br> 10 cm<br> 12 cm<br> What is the surface area of the triangular prism?
    10·1 answer
  • 1. Solve the equation.<br>4(x + 5) = 24<br><br>​
    8·2 answers
  • Please help me solve these problems.
    11·1 answer
  • 8 people from a group of 12
    15·2 answers
  • A baseball team has a goal of hitting more than 91 home runs this season. They average 7 home runs each game and have
    10·1 answer
  • Look at this set of 5 numbers: 21471 By how much would the mode decrease if the number 1 were added to the set?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!