Question

Match the following and select the correct option.
1
Prims's algorithm
a
Dynamic
programming
2
b
Binary search
algorithm
Divide and conquer
programming
3
Quick sort algorithm
с
Greedy programming
4
d
Traveling salesmen
algorithm
Decrease-and-
Conquer
programming
a) 1-a,2-0,3-d, 4-6
b) 1-c, 2-a, 3-6,4-d
c) 1-d,2-с,3-a, 4-6
d) 1-c,2-d,3-6,4-a

Answer 1

Answer:

List-I

A. Prim’s algorithm for minimum spanning tree

B. Floyd-Warshall algorithm for all pairs shortest paths

C. Mergesort

D. Hamiltonian circuit

List-II

1. Backtracking

2. Greed method

3. Dynamic programming

4. Divide and conquer

Codes:

A B C D

(a) 3 2 4 1

(b) 1 2 4 3

(c) 2 3 4 1

(d) 2 1 3 4

(A) a

(B) b

(C) c

(D) d

Answer: (C)

Explanation: Prim’s Algorithm is a greedy algorithm where greedy choice is to pick minimum weight edge from cut that divides already picked vertices and vertices yet to be picked.

Floyd-Warshall algorithm for all pairs shortest paths is a Dynamic Programming algorithm where we keep updating the distance matrix in bottom up manner.

Merge Sort is clearly divide and conquer which follows all steps of divide and conquer. It first divides the array in two halves, then conquer the two halves and finally combines the conquered results.

Answer 2

Explanation:

oh! my God ,what is this ?