CS502 Midterm Quiz by Smile

Fundamentals of Algorithms (CS · Multiple Choice Questions (MCQs) · Objective Questions

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

1. Not a solution
2. An algorithm
3. Good solution
4. The best solution

In ________ algorithm, at any time, the subset of edges A forms a sing

1. Kruskal's
2. Prim's
3. Both Kruskal's and Prim's
4. None of the given

Counting sort assumes that the numbers to be sorted are in the range

1. k to n where n is large
2. 1 to k where k is small
3. k to n where k is small
4. k to n where n is small

In Dynamic Programming approach, we do not store the solution to ea problem in case if it reappears.

1. True

Shortest path problems can be solved efficiently by modeling the road graph.

1. True
2. False

Adding an edge to a free tree creates.

1. A cycle
2. A complete MST
3. A partial MST
4. A shortest path

Although it requires more complicated data structures, Prim's algorithm minimum spanning tree is better than Kruskal's when the graph has a of vertices.

1. True
2. False

In Prim's algorithm, we start with the root vertex r; it can be any verte

1. True
2. False

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

1. True
2. False

According to parenthesis lemma. vertex u is a descendent of v vertex i

1. [d[u], f[u]] ⊆ [d[v], f[v]] [d[ ] f[ ]] ⊇ [d[ ] f[ ]]

Dynamic Programming is a problem-solving approach in which ______

1. Problem is solved in Zero time
2. Solution is developed only at final stage
3. Both are correct
4. Both are incorrect

Networks are ________ in the sense that is possible from any location network to reach any other location in the digraph.

1. Complete
2. Incomplete
3. Not graphs
4. Transportation

We say that two vertices u and v are mutually not reachable if u can re vice versa.

1. True
2. False

We say that two vertices u and v are mutually ________ if u can reach versa.

1. Crossed
2. Forward
3. Reachable
4. Nor Reachable

Consider three matrices X, Y, Z of dimensions 1 × 2, 2 × 3, 3 × 4 respe number of multiplications of X(YZ) is:

1. 16
2. 23