CS502 Final Term Solved MCQs with References by Moaaz

CS502- Fundamentals of Algorithms · Solved MCQS · From Final term Papers · July 10,2013 · PSMD01 · Spring 2010

Q1. An optimization problem is one in which you want to find, (1 marks)

1. Not a solution
2. An algorithm
3. Good solution
4. The best solution (Page 97)

Correct answer: The best solution (Page 97)

Q2. 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. (1 marks)

1. False

Q3. If a problem is in NP, it must also be in P. (1 marks)

1. True
2. False
3. unknown (Page 173)

Correct answer: unknown (Page 173)

Q4. What is generally true of Adjacency List and Adjacency Matrix representations of graphs? (1 marks)

1. Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
2. Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)
3. Lists require more space than matrices and they take longer to find the weight of an edge (v1,v2)
4. Lists require more space than matrices but are faster to find the weight of an edge (v1,v2)

Correct answer: Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

Q5. If a graph has v vertices and e edges then to obtain a spanning tree we have to delete (1 marks)

1. v edges.
2. v – e + 5 edges
3. v + e edges.
4. None of these

Correct answer: None of these

Q6. Maximum number of vertices in a Directed Graph may be |V2| (1 marks)

1. True

Q7. The Huffman algorithm finds a (n) _____________ solution. (1 marks)

1. Non-optimal
2. Exponential
3. Polynomial

Q8. The Huffman algorithm finds an exponential solution (1 marks)

1. True
2. False

Correct answer: False

Q9. The Huffman algorithm finds a polynomial solution (1 marks)

1. True
2. False

Correct answer: False

Q10. The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency. (1 marks)

1. True
2. False (Page 100)

Correct answer: False (Page 100)

Q11. The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other. (1 marks)

1. True (Page 101)
2. False

Correct answer: True (Page 101)

Q12. Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string. (1 marks)

1. True
2. False (Page 102)

Correct answer: False (Page 102)

Q13. Shortest path problems can be solved efficiently by modeling the road map as a graph. (1 marks)

1. True (Page 153)
2. False

Correct answer: True (Page 153)

Q14. Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles. (1 marks)

1. True
2. False (Page 159)

Correct answer: False (Page 159)

Q15. Bellman-Ford allows negative weights edges and negative cost cycles. (1 marks)

1. True
2. False (Page 159)

Correct answer: False (Page 159)

Q16. The term “coloring” came form the original application which was in architectural design. (1 marks)

1. True
2. False (Page 176)

Correct answer: False (Page 176)

Q17. In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other. (1 marks)

1. True (Page 176)
2. False

Correct answer: True (Page 176)

Q18. Dijkstra’s algorithm is operates by maintaining a subset of vertices (1 marks)

1. True (Page 155)
2. False

Correct answer: True (Page 155)

Q19. The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key. (1 marks)

1. True ( Page 156)
2. False

Correct answer: True ( Page 156)