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 coloring 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