Question: Consider a directed acyclic graph with V vertices and E edges. (i) What is meant by a total order on the vertices consistent with the

Consider a directed acyclic graph with V vertices and E edges.

(i) What is meant by a total order on the vertices consistent with the edges? [2 marks]

(ii) Describe an O(E + V ) algorithm to compute such a total order. [3 marks]

(b) Consider a directed graph with non-negative edge costs and with a given start vertex s.

(i) Dijkstra’s algorithm computes distances from s to every other vertex. Give psuedocode for Dijkstra’s algorithm. [4 marks]

(ii) Dijkstra’s algorithm can be implemented using a Fibonacci heap. State the complexity of using this implementation. Justify your answer carefully. [Note: Your answer should include mention of amortized costs.] [4 marks]

(c) Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s.

(i) Devise an algorithm to compute distances from s in O(E +V ) time. Justify why your algorithm is correct. [4 marks]

(ii) Explain, with an example, why Dijkstra’s algorithm might take ?(V log V ) time. [3 marks]

Step by Step Solution

★★★★★

3.46 Rating (159 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock

The detailed answer for the above question is provided below a i A total order on the vertices of a directed acyclic graph DAG is a linear ordering of the vertices such that for every edge u v in the ... View full answer

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Algorithms Questions!

Q:

What is meant by the total value concept?

Q:

In your own words, describe what is meant by an authentic leader. How does this differ from previous theories, and why may it be so important now?

Q:

Describe in your own words what is meant by Goldratts critical chain. How does it work?

Q:

You have been provided with the description of a programming language, J, intended for scripting applications. Its syntax is similar to a cut-down version of Java in that it consists of function...

Q:

explain (a) Describe how mutual-exclusion locks provided by the synchronized keyword can be used to control access to shared data structures. In particular you should be clear about the behaviour of...

Q:

) Explain the collision detection mechanism applied in standard wired medium access control associated with CSMA and indicate why this might be unsuitable for wireless networks. [2 marks] (ii)...

Q:

In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...

Q:

State what is meant by a directed graph and a strongly connected component. Illustrate your description by giving an example of such a graph with 8 vertices and 12 edges that has three strongly...

Q:

Let i and j be positive integers. (i) Prove that there exist natural numbers a and b such that ai = bj+gcd(i, j). You may use standard results provided that you state them clearly. [4 marks] (ii) Let...

Q:

In this question you will be asked to reflect on a project you have been involved in or observed, in which a design evolved, or could have evolved, through applying a theory of user behaviour. You...

Q:

Risk Reduction Create an Excel spreadsheet to organize your answers to the following problem. A company is considering the following two dividend policies for the next five years. Year Policy #1...

Q:

Explain 41. If a transfer price of P 84 is determined using the transfer pricing formula and the lost contribution margin per unit on outside sales is P 28, then the variable cost per unit must be...

Q:

Bintang has arranged to purchase a house costing (Indonesian rupiaya) IDR2 million on a Murabaha basis from Indonesia Islamic Bank. All other indirect costs of acquiring the property are IDR50,000....

Q:

One scientist is measuring a physical quantity on a strange unit. For example, the time taken by the light to travel from a star to the earth was measured in units "BRT". If this unit has to make...

Q:

What is the variance and standard deviation of of 46.38, 46.18, 46.57, 46.72, 46.86, 46.58, 46.61, 46.64, 46.03, 45.93, 45.51, 45.53

Q:

Money Inc., a USA-based business has an acid test ratio of 3 times, and the value of the current assets including closing inventories (comprising of trade receivables of $2,000,000 and cash of...

Q:

if assets decrease an equity increases what is the formula to find total liabilities

Q:

Discuss the concept of the looking-glass self. how do you think others perceive you? do you think most people perceive you correctly?

Q:

As written, each loop iteration in the LIST-SEARCH procedure requires two tests: one for x L.nil and one for x.key k. Show how to eliminate the test for x L.nil in each iteration.

Q:

Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T(1) = 1 for recurrence (4.19) without adjusting the boundary conditions for the...

Q:

The reduction algorithm F in the proof of Lemma 34.6 constructs the circuit C = f (x) based on knowledge of x, A, and k. Professor Sartre observes that the string x is input to F, but only the...

Q:

A home owner with a large library needs to estimate the purchase cost and replacement value of the book collection for insurance purposes. She has 44 shelves containing books, and selects 12 shelves...

Q:

Use the file statepop.dat for this problem. a. Plot the total number of veterans versus the probabilities of selection i. Does your plot indicate that unequal-probability sampling will be helpful...

Q:

Show that (6.28) and (6.29) are equivalent when an SRS of psus is selected as in Chapter 5. Are they equal if psus are selected with unequal probabilities?