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
Simplify. 9x^8-18x^6
GrogVix [38]
You cannot simplify this but you can factorise it:

9x^6 (x^2 - 2)
7 0
3 years ago
Fatima drove 100 miles in 4 hours. What is the constant of proportionality for 100 miles in 4 hours and 200 miles in 8 hours? Pl
Helen [10]

Answer:

25

Step-by-step explanation:

4 hours goes into 100 miles 25 times.

3 0
2 years ago
Bill went to the museum at 11:30 A.M . He stayed for 3 1/2 hours.When did he leave ?
tatuchka [14]
To start, note that an hour is 60 minutes long. A 1/2 hour, or half hour, is then 60/2=30 minutes. Therefore, when we have 11 hours and 30 minutes, we have 11 and a half hours. Adding 3 and a half to that, we get 11.5+3.5=15 (a half can also be expressed as .5, although it's not typically done that way when expressing time - it just might be easier to visualize it this way). Therefore, we are 15 hours into the day. However, we can't just stop there - we have to account for AM and PM. Therefore, we subtract 12 hours from 15. If the number is positive, we are in PM - otherwise, we're in AM. Therefore, as 15-12=3, the time is in PM. The remaining number is the time, so Bill leaves at 3 PM. If we are left with a decimal (e.g. 3.25), we would keep the 3 and multiply the 0.25 (the decimal) by 60 to figure out how many minutes we have, so 3.25 would turn into 3+0.25*60=3:15.

Feel free to ask further questions!
5 0
3 years ago
5=g/8 PLRASE HELP Me
pantera1 [17]

G= 40

5x8=40

40/8=5

All you have to do is inverse operations so instead of dividing you multiply your 5 and 8 to get 40 and then check your work.

4 0
3 years ago
Helpppppp meeeee plllleeeaasss
g100num [7]
The rate is 12 per carton.
4 0
2 years ago
Read 2 more answers
Other questions:
  • Ryan bought a digital camera with a list price of $150 from an online store offering a 5% discount. He needs to pay $5.50 for sh
    12·2 answers
  • A decimal is a fraction that has a denominator of 100 is it sometimes, always or never​
    10·2 answers
  • Using data set from 1.19
    9·1 answer
  • It takes 124 minutes to lift 4 tires on to a lorry how long would it take him to fit 6 tires in a lorry
    11·1 answer
  • Sammy and his family took a hiking trip to the mountains. They started out with 20 pounds of food. They plan on eating 4 pounds
    9·1 answer
  • What is the best next step in the construction of a line that passes through B and is perpendicular to line A?
    10·1 answer
  • You have 18 tbsp of onion powder you need 2 tbsp to make one serving of spice rub how many servings can you make
    15·2 answers
  • In a class of 20 students, the number of boys was the number of girls. How many girls were in the class?
    9·1 answer
  • Doe anyone know this? At least someone have to
    9·1 answer
  • Find all x-intercepts and y-intercepts of the graph of the function.<br> F(x)=x³-4x² - 4x + 16
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!