Although it requires more complicated data structures, Prim's algorithm for a minimum spanning tree is better than Kruskal's when the graph has a large number of vertices?
a) True
b) False
c) NA
d) N/A
In Prim's algorithm, the additional information maintained by the algorithm is the length of the shortest edge from vertex v to points already in the tree?
a) True
b) False
c) NA
d) N/A
Suppose that a graph G = (V,E) is implemented using adjacency
lists. What is the complexity of a breadth-first traversal of G?
a) O(|V |^2)
b) O(|V| |E|)
c) O(|V|^2|E|)
d) O(|V| + |E|)
A dense undirected graph is?
a) A graph in which E = O(V^2)
b) A graph in which E = O(V)
c) A graph in which E = O(log V)
d) All items above may be used to characterize a dense undirected graph
Which is true statement?
a) Breadth first search is shortest path algorithm that works on un-weighted graphs
b) Breadth first search is shortest path algorithm that works on un-weighted graphs
c) Both of above are true
d) None of above are true
Which statement is true?
a) If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is globally optimal
b) If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally optimal
c) both of above
d) none of above
