Question 1 |

Suppose you have a directed acyclic graph with n vertices and O(n) edges, all having
nonnegative weights. Running time (in form of n) of an efficient algorithm for finding the shortest path to each
vertex from a single source is

O(n) | |

O(n \log n) | |

O(n^2) | |

O(n^2 \log n) |

Question 1 Explanation:

The given conditions allow us to use either the DAG shortest paths algorithm or Dijkstra's. DAG shortest paths runs in \Theta (V+E)=\Theta (n), and Dijkstra's
runs in O((V + E) \log V ), or O(V \log V + E) if using a Fibonacci heap. In either case,
Dijkstra's runs in O(n \log n). DAG shortest paths is faster in this case

https://www.cs.bgu.ac.il/~ds182/wiki.files/14-shortest_paths.pdf

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

https://www.cs.bgu.ac.il/~ds182/wiki.files/14-shortest_paths.pdf

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 2 |

Which of the following Statemets is/are TRUE?

S1: Consider two positively weighted graphs G = (V; E; w) and G_0 = (V; E; w_0) with the same vertices V and edges E such that, for any edge e in E , we have w_0(e) = w(e)^2 . For any two vertices u, v in V , any shortest path between u and v in G_0 is also a shortest path in G .

S2: If the priority queue in Dijkstra's algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation), then Dijkstra's algorithm would run in O(ElgV +V lgV) time.

S1: Consider two positively weighted graphs G = (V; E; w) and G_0 = (V; E; w_0) with the same vertices V and edges E such that, for any edge e in E , we have w_0(e) = w(e)^2 . For any two vertices u, v in V , any shortest path between u and v in G_0 is also a shortest path in G .

S2: If the priority queue in Dijkstra's algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation), then Dijkstra's algorithm would run in O(ElgV +V lgV) time.

S1 is True and S2 is False | |

S1 is False and S2 is True | |

S1 and S2 are False | |

S1 and S2 are True |

Question 2 Explanation:

S1 is FALSE

Assume we have two paths in G as (1) path: u-x-v : 4 with w(u,x)=2,w(x,v)=2 (2)path: u-v:3 with w(u,v)=3. The first one is shorter in G_0 while the second one is shorter in G.

S2 is FLASE

The list can take \Theta (V) time to insert a node, and there are (V) nodes to insert, for a running time of \Omega (V^2). In addition, the \Theta (E) calls to decrease-key can each take \Theta (V) time for a total running time of \Theta ((V + E)V ).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Assume we have two paths in G as (1) path: u-x-v : 4 with w(u,x)=2,w(x,v)=2 (2)path: u-v:3 with w(u,v)=3. The first one is shorter in G_0 while the second one is shorter in G.

S2 is FLASE

The list can take \Theta (V) time to insert a node, and there are (V) nodes to insert, for a running time of \Omega (V^2). In addition, the \Theta (E) calls to decrease-key can each take \Theta (V) time for a total running time of \Theta ((V + E)V ).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 3 |

Which of the following Statemets is/are TRUE?

S1: Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra's algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

S2: Dijkstra's algorithm may not terminate if the graph contains negative-weight

S1: Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra's algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

S2: Dijkstra's algorithm may not terminate if the graph contains negative-weight

S1 is True and S2 is False | |

S1 is False and S2 is True | |

S1 and S2 are False | |

S1 and S2 are True |

Question 3 Explanation:

S1 is TRUE

Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra's will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

S2 is FLASE

It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra's will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

S2 is FLASE

It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

There are 3 questions to complete.

**Suggested FREE Mock Test For you.**