(A) Only (a) & (e)
(B) Both (c) and (e)
(C) All of these
(D) Non of these
Tag: Fundamentals of Algorithms
Which of the following arrays represent descending (max) heaps? I. [10,7,7,2,4,6] II. [10,7,6,2,4,7] III. [10,6,7,2,4,6] IV. [6,6,7,2,4,10]?
(A) Only II
(B) Only IV
(C) Both II and IV
(D) Both I and III
Which statement is true (I) The running time of Bellman-Ford algorithm is T (VE) (II) Both Dijkstra’s algorithm and Bellman-Ford are based on performing repeated relaxations (III) The 0-1 knapsack problem is hard to solve?
(A) Only I
(B) Only III
(C) Both I and III
(D) All of these
If a problem is NP-complete, it must also be in NP?
(A) True
(B) False
(C) NA
(D) NA
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) NA
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) NA
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