Question

3)match the following :

1) fake coin problem A) shortest hamiltonian circuit
2) floyd warshall algorithm b) class NP
3) Traveling salesman problem c) can deal negative weight edges
4) graph colouring problem d) divide and conquer

a)1-d 2-b 3-a 4-c
b)1-b 2-c 3-a 4-d
c)1-c 2-d 3-b 4-a
d)1-d 2-c 3-a 4-b

Answer 1

1-c, 2-d, 3-b, 4-a is the correct answer I suppose

Answer 2

Answer:

C) 1-c 2-d 3-b 4-a

Explanation:

 

1) Fake Coin Problem                    – c)      Can Deal Negative Weight Edges

2) Floyd Warshall algorithm          –  d)    Divide and Conquer

Floyd Warshall Algorithm – It is a dynamic programming algorithm which finds the shortest paths using recursive nature of problem. But the correct answer  to this is Dynamic Programming paradigm and not divide and conquer.

3) Traveling salesman problem   –    b)    Class NP

NP is basically decision problems which can be solved using Non-deterministic Turing Machine in Polynomial time.

4) Graph Colouring Problem          –   a)     A shortest Hamiltonian circuit