Which of the following statement is false about Dijkstra’s Algorithm?

• A) It can be applied on graphs having a negative weight function
• B) Its implementation in data structure is possible through the priority queue
• C) It works on a weighted directed graph
• D) It is used to solve Single-source shortest path

Overall time for Kruskal algorithm is:

• A) Θ(ElogV)
• B) Θ(logE)
• C) Θ(VlogE)
• D) Θ(ElogE)

There exist a unique path between any ________ vertices of a free tree.

• A) Two
• B) Four
• C) One
• D) Three

In Timestamped DFS, If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u, we get ______________.

• A) a line
• B) a cycle
• C) nothing
• D) a graph

In computing the ____________ components of a digraph, vertices of the digraph are partitioned into subsets.

• A) best
• B) worst
• C) weakly connected
• D) strongly connected

Dijkstra’s Algorithm cannot be applied on ______________.

• A) undirected and unweighted graphs
• B) graphs having negative weight function
• C) unweighted graphs
• D) directed and weighted graphs

In Generic approach determining of Greedy MST, we maintain a subset A of __________ .

• A) Paths
• B) Cycles
• C) Vertices
• D) Edges

In Kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a/an __________ .

• A) Edge
• B) Cycle
• C) Tree
• D) Vertex

In computing the strongly connected components of a digraph, vertices of the digraph are _______ into subsets.

• A) Deleted
• B) Joined
• C) Partitioned
• D) Created

Adding any edge to a free tree creates a unique ______ .

• A) Strong component
• B) Vertex
• C) Edge
• D) Cycle

In Timestamped DFS-cycles lemma, if edge (u, v) is a tree, forward or cross edge, then _________

• A) $${\text{f[u]}} < {\text{f[v]}}$$
• B) $${\text{f[u]}} \leqslant {\text{f[v]}}$$
• C) $${\text{f[u]}} > {\text{f[v]}}$$
• D) $${\text{f[u]}} \geqslant {\text{f[v]}}$$

As the Kruskal's algorithm runs, the edges in viable set A induce a _________ on the vertices.

• A) Set
• B) Tree
• C) Forest
• D) Graph

In ________ algorithm(s), at any time, the subset of edges A forms a single tree.

• A) kruskal's and Prim's
• B) BFS
• C) Kruskal's
• D) Prim's

The relationship between number of back edges and number of cycles in DFS is,

• A) Back edges are one quarter of cycles
• B) Back edges are half of cycles
• C) Both are equal
• D) There is no relationship between no. of edges and cycles

You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?

• A) E
• B) V.E
• C) V
• D) (V+E)

In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.

• A) Trees
• B) Vertices
• C) Edges
• D) Both edges & vertices

The tricky part of __________ algorithm(s) is/are, how to detect whether the addition of an edge will create a cycle in viable set A.

• A) Prim's
• B) Kruskal's
• C) Both Krusal's and Prim's
• D) DFS

An edge (u, v) _______ E − A is safe if A _______{(u, v)} is viable.

• A) ϵ,П
• B) ϵ,U
• C) П,U
• D) U,ϵ

Dijkstra’s Algorithm is used to solve____________problems.

• A) Sorting & searching
• B) Multi-source shortest path
• C) Single-source shortest path
• D) All-pair shortest path

Which activity creates a unique cycle in a free tree:

• A) adding any edge
• B) adding any sub tree
• C) adding any vertex
• D) adding root