AOA Quiz

Dijkstra’s algorithm is used to solve __________  problems?

• Network lock

• All pair shortest path problem

• Single source shortest path problem

• Sorting

Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider-

n = 5

w = 60 kg

(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)

(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)

• 210

• 220

• 240

• 230

Differentiate between Dynamic Programming and Divide & Conquer strategy.

Which of the following is used for solving the N Queens Problem?

• Greedy Algorithm

• Backtracking

• Branch and Bound

• Dynamic Programming

Which of the following sorting algorithms provide the best time complexity in the worst-case scenario?

• Merge Sort

• Quick Sort

• Selection sort

• Bubble sort

What is the drawback of Bellman ford algorithm?

Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach. Consider-

n = 4

w = 5 kg

(w1, w2, w3, w4) = (2, 3, 4, 5)

(b1, b2, b3, b4) = (3, 4, 5, 6)

• 6

• 5

• 8

• 7

Given two sequences of characters, P=<MLNOM> Q=<MNOM>. Obtain the longest common subsequence and also find length of LCS.

• MNOM, 4

• NOM,3

• OM, 2

• LNOM,4

Identify the approach followed in Floyd Warshall’s algorithm?

• Dynamic Programming

• Divide & Conquer

• Backtracking

• Greedy approach

Solve the sum of subset problems using backtracking algorithmic strategy for the following data: n = 4 W =(w1, w2, w3, w4) = (11, 13, 24, 7) and M = 31.

• {1,0,0,1} ,{0,0,1,1}

• {1,1,0,1} ,{0,0,1,1}

• {1,1,0,1} ,{0,1,1,1}

• {1,1,0,1} ,{1,1,0,0}