Answer the following questions about a backtracking algorithm for the Travelling Salesman Problem.

3. What would be the states and transitions in a backtracking algorithm for TSP?

4. Given a set of candidates transitions to make, which candidate would you explore first and why?

The following questions are about a reduction between the Hamiltonian Cy- cle problem (HC) and the Travelling Salesman Problem (TSP). HC is a problem where you and given an unweighted graph, and the solution is whether the graph contains a cycle with every vertex. Meanwhile, TSP is a problem where you are given a weighted graph and a threshold k, and the solution to TSP is whether the graph contains a cycle with every vertex of weight k or less. Input: G (V. E): unweighted graph with n vertices and m edges Input: n, m: order and size of G Output: whether G has a Hamiltonian Cycle 1 Algorithm: HCReduction 2 H WeightedGraph(n) 3 for u E V do 4 forvEV do if G.isAdjacent(u, v) then | H.addEdge(u, v, 1) else if u u then | H.addEdge(u, v, 2) en 10 end 11 end 12 return TSP (H, n)