For this exercise you are asked to solve the “Traveling Salesman Problem”: given a complete, undirected weighted graph of N>2 vertices you have to find the minimum Hamiltonian cycle. A Hamiltonian cycle is a cycle that visits all vertices exactly once (with the exception of the first and last vertex). You can assume that the weights are positive, but you cannot assume that the weights obey the triangle inequality.

This programming assignment will help you acquire practical experience with dynamic programming. You are asked to implement a dynamic programming algorithm that solves the optimal cheque writing problem.