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
A ceramic vase that cost an antique store $5 was marked $20. what is the percentage markup on the price of the ceramic vase?
VikaD [51]
20/25 × 10% = 80%

the answer is 80%
3 0
2 years ago
What is four points fewer than the bulls scored write in a algebraic expression
Elena-2011 [213]
B - 4   where B is the variable representing the Bulls score
4 0
2 years ago
Read 2 more answers
A bank manager is interested in the average length of time that customers are willing to wait in line before they give up and le
Fynjy0 [20]

Answer: The average length of time that the 25 customers waited before leaving the bank.   <u> e. Statistic</u>

The list of times for the 25 customers who left the bank.  <u> f.Data </u>

All of the bank's customers                                         <u> d. Population</u>

The 25 customers that the manager observed leave.         <u> c. Sample</u>

The length of time a customer waits before leaving the bank.  a. <u>Variable.</u>

The average length of time that all customers will wait before leaving the bank <u>a. Parameter</u>

Step-by-step explanation:

A data is a list of observations.

In statistics, a variable is an attribute that defines  a person, place, thing, or thought.

A large group that have similar individuals as per the researcher's point of view is known as population, where its subset is known as sample.

The measure of certain characteristic in population is known as parameter, where for sample it is known as statistic.

8 0
3 years ago
The graph of y = x 2 has been translated 7 units to the left. The equation of the resulting parabola is _____.
strojnjashka [21]
To move the function to the left you have to increase x inside the function
think of it like g(x)=f(x+7)

the solution is
y=(x+7)^2
6 0
3 years ago
Read 2 more answers
_______are the possible results of an experiment
Virty [35]
Outcome

Hope this helps :)

6 0
2 years ago
Other questions:
  • What is the simplest fraction for 57/76?
    10·1 answer
  • Which function describes the table of values?
    5·1 answer
  • Consider the enlargement of the rectangle. A smaller rectangle with length of x inches and width of three-fifths inch. A larger
    12·2 answers
  • Peter has been saving his loose change for several days. When he counted his quarters and dimes, he found they had a total value
    13·2 answers
  • 206 MAI
    15·1 answer
  • Where was George Washington born
    7·2 answers
  • How many cubic inches of storage space are in Leo’s cabinet ? Please help :)
    8·1 answer
  • Mrs. Moore's third grade class wants to go on a field trip to the science museum.
    8·1 answer
  • Find the shortest length of wood that can be cut into equal lengths of 3m. 8<br>and 12m​
    5·1 answer
  • For each of the following functions, evaluate: f(-4), f(-2), f(0), f(2), and f(4)
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!