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
Nadusha1986 [10]
3 years ago
8

Suppose we are given an arbitrary digraph G = (V, E) that may or may not be a DAG. Modify the topological ordering algorithm so

that given an input G, it outputs one of the two things: a. A topological ordering thus establishing that G is a DAG. b. A cycle in G thus establishing that it is not a DAG. The runtime of your algorithm should be O(m+n) where m = |E| and n = |V|
Computers and Technology
1 answer:
lianna [129]3 years ago
3 0

Answer:

Check the explanation

Explanation:

We can utilize the above algorithm with a little in modification. If in each of the iteration, we discover a node with no inward edges, then we we’re expected succeed in creating a topological ordering.

If in a number of iteration, it becomes apparent that each of the node has a minimum of one inward edge, then there must be a presence of cycle in the graph.

So our algorithm in finding the cycle is this: continually follow an edge into the node we’re presently at (which is by choosing the first one on the adjacency list of inward edges to decrease the running time).

Since the entire node has an inward edge, we can do this continually or constantly until we revisit a node v for the first time.

The set of nodes that we will come across among these two successive visits is a cycle (which is traversed in the reverse direction).

You might be interested in
Dr. Joon asks her students how to insert a table in an Excel workbook. The students record the steps a chart. Which students lis
Leona [35]

Answer:

C

Explanation:

Both Table and Format as Table can be used to create a table

4 0
3 years ago
Suppose for the worst case, given input size n: Algorithm 1 performs f(n) = n2 + n/2 steps Algorithm 2 performs f(n) = 12n + 500
melomori [17]

Answer:

29

Explanation:

for n=28:

--------------

Algorithm 1 performs f(n) = n2 + n/2 = 28*28 + 28/2 = 798

Algorithm 2 performs f(n) = 12*28 + 500 = 836

for n=29

--------------

Algorithm 1 performs f(n) = n2 + n/2 = 29*29 + 29/2 = 855.5

Algorithm 2 performs f(n) = 12*29 + 500 = 848

so, for n=29, algorithm 2 will be faster than algorithm 1

6 0
3 years ago
Mr. Lee wants to show his class a presentation. Which device will display an enlarged view of his presentation?
Gnesinka [82]
A projector would make his presentation bigger.<span />
3 0
3 years ago
Does the wireless signal between the cell phones require matter to travel from one phone to another?
mrs_skeptik [129]

Mobile phones transmit and receive signals using electromagnetic waves, that is, wireless signal are electromagnetic waves which can travel through a vacuum, they do not need a medium or matter.

<h3>What are electromagnetic waves?</h3>

They are generated by electrical and magnetic particles moving at the same time (oscillating).

<h3>Characteristics of electromagnetic waves</h3>

  • Network waves are electromagnetic waves.

  • A mobile phone has coverage when it receives electromagnetic waves from at least one base station.

  • They do not necessarily require a material medium for their propagation.

Therefore, we can conclude that electromagnetic waves are those that do not need a material medium to propagate and include, among others, radio, television and telephone waves.

Learn more about electromagnetic waves here: brainly.com/question/13803241

3 0
2 years ago
You have just installed the microsoft windows 7 operating system on your pc. which web browser is bundled with windows 7 and is
kirill [66]
The web browser that is automatically installed with windows 7 is Internet Explorer.

Hope this helps.
6 0
3 years ago
Other questions:
  • Data cannot be sorted of filtered accurately if there are ________.
    10·2 answers
  • Which of the following is considered to be intellectual property?
    9·1 answer
  • Hello everyone. I need help. C programming. Create at least two more functions except the main () function to collect them.
    5·1 answer
  • I stole you pokemon cards :o
    6·2 answers
  • you have a small network in your business with just a few network devices connected along with 22 linux computers and you want t
    7·1 answer
  • Many instruction sets contain the instruction NOOP, meaning no operation, which has no effect on the processor state other than
    14·1 answer
  • What is internet marketing??
    13·1 answer
  • Explain what happens if you try to open a file for reading that does not exist.
    10·1 answer
  • Display the total number of parking tickets.
    5·1 answer
  • What is computer?explain any five characteristic in short.​
    9·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!