## Description

Assignment: NP-Completeness and Heuristic Algorithms

1. NP-Completeness: Consider the Travelling Salesperson (TSP) problem that was covered in

the exploration.

Problem: Given a graph G with V vertices and E edges, determine if the graph has a TSP

solution consisting of a cost k.

Prove that the above stated problem is NP-Complete

2. Implement Heuristic Algorithm:

a. Below matrix represents the distance of 5 cities from each other. Represent it in the

form of a graph

A B C D E

A 0 2 3 0 0

B 2 0 15 2 0

C 3 15 0 0 13

D 0 2 0 0 9

E 0 0 13 9 0

b. Apply Nearest-neighbour heuristic to this matrix and find the approximate solution

for this matrix if it were for TSP problem.

c. What is the accuracy ratio of your approximate solution?

d. Write the pseudocode for the nearest neighbour heuristic

———————-(Ungraded question: you can try this question if time permits)—————

Implement the Minimum Spanning Tree-based approach for the TSP problem that was discussed in

the exploration. Name your function approx_tsp_algo(G). Name your file TSP.py

Debriefing (required!): ————————–

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?

4. Any other comments?

Note: ‘Debriefing’ section is intended to help us calibrate the assignments.