CS502 MCQs and Important Topics by Junaid

CS02 for final term important mcqs and Topic

Q1. The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.

(REP)

•  True

 False

GOOGLE

Q2. Dijkstra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.

(REP)

•  True

 False

Pg159

Q3. Dijkestra s single source shortest path algorithm works if all edges weights are non-negative and there are no negative cost cycles.

(REP)

•  TRUE pg159
•  FALSE

Q4. Dijkstra s single source shortest path algorithm works if all edges weights are negative and there are no negative cost cycles.

(REP)

•  True

 False

pg159

Q5. Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the algorithm is in the clever recursive formulation of the shortest path problem.

(REP)

•  True

(p162)

•  False

Q6. Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive evaluation by generating a table for dij

(k)

(REP)

•  TRUE

pg164

 FALSE

Q7. The term coloring came from the original application which was in map drawing (REP)

•  True

pg173

 False

Q8. The term “coloring ” came from the original application which was in architectural design

(REP)

•  True

 False

pg173

Q9. In the clique cover problem, for two vertices to be in the same group, they must be _____ each other.

(REP)

•  Apart from
•  Far from
•  Near to

 Adjacent to

(p176)

Q10. In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.

(REP)

•  True pg176
•  False

Q11. In the clique cover problem, for two vertices to be in the same group, they must be apart from each other.

(REP)

•  True
•  False pg176

Q12. The difference between Prims algorithm and Dijkstra s algorithm is that Dijkstra s algorithm uses a different key.

(REP)

•  True pg156
•  False

Q13. The difference between Prims algorithm and Dijkstra s algorithm is that Dijkstra s algorithm uses a same key

(REP)

•  True pg156
•  False

Q14. You have an adjective list for G, what is the time complexity to computer graph transpose G^T.? (REP)

V+E pg138

Q15. Given an adjacency list for G, it is possible to compute G T in Θ(V + E) time. (REP)

It takes O(log V) to extract a vertex from the priority queue.

Q16. Overall time for Kruskal is Θ(E log E) = Θ(E log V) if the graph is sparse. (REP)

•  True pg149
•  False

Q17. An optimization problem is one in which you want to find, (REP)

•  Not a solution
•  An algorithm
•  Good solution

 The best solution

pg197

Q18.  True

Conceptual

 False

Q19. If a graph has v vertices and e edges then to obtain a spanning tree

we have to (REP)

•  delete v edges.
•  v – e + 5 edges
•  v + e edges.