CS502|FUNDAMENTALS OF ALGORITHM|QUIZ SOLUTION by AYNA's Math Treasure

CS502|FUNDAMENTALS OF ALGORITHM|QUIZ SOLUTION

1.      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.

CORRECT:-       True

2.     What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

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

3.     An optimization problem is one in which you want to find,

CORRECT:-       The best solution

4.     If a problem is in NP, it must also be in P.

CORRECT:-       Unknown

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

CORRECT:-       False

6.     The Huffman algorithm finds a polynomial solution

CORRECT:-       False

7.     The Huffman algorithm finds an exponential solution

CORRECT:-       False

8.     The Huffman algorithm finds a (n) _____________ solution.

CORRECT:-       Optimal

9.     Maximum number of vertices in a Directed Graph may be |V2 |

CORRECT:-       False

10.   If a graph has v vertices and e edges then to obtain a spanning tree we have to delete

CORRECT:-       None of these

11.   Bellman-Ford allows negative weights edges and negative cost cycles.

CORRECT:-       False

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

CORRECT:-       False

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

CORRECT:-       False

14.   Shortest path problems can be solved efficiently by modeling the road map as a graph.

CORRECT:-       True

15.   The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.

CORRECT:-       True

16.   The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key

CORRECT:-       True

17.   Dijkstra’s algorithm is operates by maintaining a subset of vertices

CORRECT:-       True

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

CORRECT:-       True

19.   The term “coloring” came form the original application which was in architectural design

CORRECT:-       False

20.   We do sorting to,

CORRECT:-       keep elements in increasing or decreasing order

21.   Dynamic programming algorithms need to store the results of intermediate sub-problems.

CORRECT:-       True

22.   In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.

CORRECT:-       Copy

23.   After partitioning array in Quick sort, pivot is placed in a position such that

CORRECT:-       Values smaller than pivot are on left and larger than pivot are on right

24.   Merge sort is stable sort, but not an in-place algorithm

CORRECT:-       True

25.   A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute

CORRECT:-       O (q)

cs502 solved quiz

Vu solved quiz

solved quiz of cs502

Solved quiz of cs502 with correct answer

cs502 quiz 2022

cs502 quiz fall 2022

cs502 quiz spring 2022