Introduction I will talk about P vs NP, NP-complete, and NP-hard, define heuristics in computer science, Hamiltonian cycles, TSP and Metric TSP, approximation algorithms, and optimal vs suboptimal solutions. I will also mention local minima, combinatorial explosion, and why exact solutions become infeasible. Finally, we will see an optimal solution and also an approximation algorithm. I’ll also discuss the limitations of the chosen approximation algorithm, what could be improved, and mention other options like MST-based solutions, k-opt methods, and metaheuristics such as genetic algorithms, and their trade-offs. The project code and analysis were developed in collaboration with Matheus Persch as part of the DSA III class at Federal University of Pelotas (UFPel) , Brazil. Prerequisites Types of problems Decision problem: You want to answer yes or no. E.g. “Is there any Hamiltonian cycle in this graph G?” (YES/NO) Search problem: You want to find a valid solution (if it exists). E.g.…