Algorithms MCQs - Greedy, Dynamic Programming, Backtracking and NP-Completeness (Set 2)

Q1. In the greedy algorithm for the activity selection problem, which activity is chosen at each step among those compatible with the ones already chosen?

a) The activity with the earliest start time

b) The activity with the shortest duration

c) The activity with the earliest finish time

d) The activity that overlaps with the fewest others

Q2. Which statement about the knapsack problem is correct?

a) Fractional knapsack is solved optimally by a greedy choice on value/weight ratio, but 0/1 knapsack is not

b) Both versions are solved optimally by the greedy value/weight ratio method

c) 0/1 knapsack is solved greedily while fractional knapsack needs dynamic programming

d) Both versions are NP-complete

Q3. Which data structure does Kruskal's algorithm use to efficiently check whether adding an edge would create a cycle?

a) Stack

b) Disjoint-set (union-find)

c) Max-heap of vertices

d) Queue

Q4. Why can Dijkstra's algorithm give wrong shortest-path distances on a graph with negative-weight edges, even when there is no negative cycle?

a) It cannot handle directed graphs

b) It works only on trees

c) It runs in exponential time on such graphs

d) Once a vertex is finalised it is never updated, but a later negative edge could give it a shorter path

Q5. If all edge weights in a connected undirected graph are distinct, then:

a) The graph has exactly one spanning tree

b) The minimum spanning tree is unique

c) Prim's and Kruskal's algorithms may give MSTs of different total weight

d) The heaviest edge can never be part of the MST

Q6. If some NP-complete problem is shown to be solvable in polynomial time, then:

a) P = NP

b) P != NP is proved

c) Only that problem moves to P; the others are unaffected

d) Every NP-hard problem, including undecidable ones, becomes solvable in polynomial time

Q7. How many distinct solutions does the 4-Queens problem have on a 4 x 4 board?

a) 0

b) 1

c) 2

d) 4

Q8. How does the Bellman-Ford algorithm detect a negative-weight cycle reachable from the source?

a) Some distance becomes zero after V - 1 passes

b) The algorithm takes more than O(VE) time

c) Dijkstra and Bellman-Ford give different answers

d) Some edge can still be relaxed after V - 1 passes

Q9. After running the Floyd-Warshall algorithm on a directed graph, how can we tell that the graph contains a negative-weight cycle?

a) dist[i][i] < 0 for some vertex i

b) dist[i][j] = infinity for some pair

c) dist[i][j] = dist[j][i] for all pairs

d) All diagonal entries remain zero

Q10. The dynamic programming solution to 0/1 knapsack runs in O(nW) time. Why is it called pseudo-polynomial?

a) Because it uses recursion with memoisation

b) Because it works only when n is small

c) Because the running time depends on the numeric value W, which is exponential in the number of bits needed to write W

d) Because its space is polynomial but its time is exponential in n

Q11. The activities below are given as (start, finish). An activity may start exactly when the previous one finishes. What is the maximum number of mutually compatible activities?

A1 (1, 3)    A2 (2, 5)    A3 (4, 6)    A4 (6, 8)
A5 (5, 9)    A6 (8, 10)   A7 (9, 11)   A8 (10, 12)

a) 4

b) 5

c) 6

d) 3

Q12. A knapsack of capacity 20 and the items below are given. What is the maximum value using fractional knapsack?

Item   Value   Weight
I1     30      5
I2     40      10
I3     45      15
I4     18      9

a) 70

b) 75

c) 88

d) 85

Q13. Characters A, B, C, D and E occur 10, 15, 30, 5 and 40 times respectively in a 100-character message. How many bits does Huffman coding need to encode the whole message?

a) 205

b) 210

c) 200

d) 300

Q14. What is the length of the longest common subsequence of X = BACDB and Y = BDCB?

a) 2

b) 3

c) 4

d) 5

Q15. A set contains {3, 5, 7, 8, 11}. Using each element at most once, which target sum CANNOT be formed by any subset?

a) 21

b) 24

c) 17

d) 29

Q16. Four matrices A (5 x 10), B (10 x 3), C (3 x 12) and D (12 x 5) are to be multiplied. What is the minimum number of scalar multiplications needed?

a) 405

b) 330

c) 580

d) 630

Q17. To prove that a new decision problem X is NP-hard, we should:

a) Reduce X to a known NP-complete problem in polynomial time

b) Show that a solution of X can be verified in polynomial time

c) Give an exponential-time algorithm for X

d) Reduce a known NP-complete problem to X in polynomial time

Q18. Which of the following problems is NP-hard but NOT in NP?

a) 3-SAT

b) Vertex cover (decision version)

c) Halting problem

d) 2-SAT