Greedy Strategy Interview Question Part 5

44. The minimum spanning tree of a graph give the shortest distance between any 2 specified nodes.(True or False)
Ans. False
Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

45. Dijkstra’s algorithm solves the _____________ shortest path problem.
Ans. single- source

46. The time required to run Dijkstra’s algorithm is ___________
a. O( ElogV)
b. O( |E| logV)
c. O( |E| log |V| )
d. O( log V)
Ans. c


47. Dijkstra algorithm finds the shortest path from a source to all the other nodes in a
weighted graph. Can you use Dijksta algorithm to find the shortest path from a source
node to all the other nodes in non-weighted graph?
a) No, because I wouldn’t know which edge to include in the cloud at each step
b) Yes, I could associate weight 0 to each edge and apply Dijkstra
c) No, because I wouldn’t be able to label the nodes
d) Yes, I could associate weight 1 to each edge and apply Dijkstra ***
e) None of the above




48. Suppose I want to find a spanning tree of a ring graph (see an example of ring graph
below) represented by an adjacency list. Can I use a BFS traversal? What would be the
complexity of BFS traversal as a function of n (number of nodes)?
a) yes, for a ring with n nodes the complexity would be always O(n) ***
b) yes, for a ring with n nodes the complexity would be always O(n2)
c) yes, for a ring with n nodes the complexity would be O(n2) in the worst case
d) yes, for a ring with n nodes the complexity would be O(n log n)
e) no, BFS is an algorithm to visit the nodes, not to construct a spanning tree. I could use
Prim to construct a spanning tree


49. What would be the complexity of Prim algorithm on a graph with n nodes and m
edges, if the priority queue is implemented with a sorted sequence based on an array.
a) O(n2+ n)
b) O(n2 + m)
c) O( n + mn)
d) O( n + n2)
Ans:c

50. You are given the following graph. If you use Dijkstra algorithm from node v you
will obtain a shortest path spanning tree from v. Which of the following algorithms
could also create a shortest path spanning tree starting from node v?
a) DFS and BFS
b) Prim and BFS
c) BFS only
d) DFS only
Ans:b