What is the time complexity of Huffman Coding?
(A) O(N)
(B) O(NlogN)
(C) O(N(logN)^2)
(D) O(N^2)

Which of the following is true about Kruskal and Prim MST algorithms? Assume that Prim is implemented for adjacency list representation using Binary Heap and Kruskal is implemented using union by rank.
(A) Worst case time complexity of both algorithms is same.
(B) Worst case time complexity of Kruskal is better than Prim
(C) Worst case time complexity of Prim is better than Kruskal

Which of the following is true about Huffman Coding.
(A) Huffman coding may become lossy in some cases
(B) Huffman Codes may not be optimal lossless codes in some cases
(C) In Huffman coding, no code is prefix of any other code.
(D) All of the above

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (GATE CS 2004)


(A) P, Q, R, S, T, U
(B) P, Q, R, U, S, T
(C) P, Q, R, U, T, S
(D) P, Q, T, R, U, S

Traversal of a graph is different from tree because
(A) There can be a loop in graph so we must maintain a visited flag for every vertex
(B) DFS of a graph uses stack, but inorrder traversal of a tree is recursive
(C) BFS of a graph uses queue, but a time efficient BFS of a tree is recursive.
(D) All of the above

What are the appropriate data structures for following algorithms?

1) Breadth First Search 2) Depth First Search 3) Prim's Minimum Spanning Tree 4) Kruskal' Minimum Spanning Tree 

(A)

1) Stack2) Queue3) Priority Queue4) Union Find

(B)

1) Queue2) Stack3) Priority Queue4) Union Find

(C)

1) Stack2) Queue3) Union Find4) Priority Queue 

(D)

1) Priority Queue2) Queue3) Stack4) Union Find

Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?
(A) Depth First Search
(B) Breadth First Search
(C) Prim’s Minimum Spanning Tree Algorithm
(D) Kruskal’ Minimum Spanning Tree Algorithm

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is


(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR