Consider the following TSP problem.

Input: Given are a set of n cities V and the distances between each pair of cities

d : V $\backslash$times V $->$ Z$>=0.$ Note that $(1)$ for any two cities a$,$ b in V $,$ d$($a$,$ b$)=$ d$($b$,$ a$)$ is a nonnegative integer and maxa,b in V d$($a$,$ b$)$ in O$($n

k

$)$ where k is a constant; $(2)$ for any three

cities i$,$ j$,$ k in V $,$ d$($i$,$ k$)$ d$($k$,$ j$)<=$ d$($i$,$ j$)<=$ d$($i$,$ k$)+$ d$($k$,$ j$).$

Output: Find the length of the shortest path that visits all cities exactly once and

returns to the origin city.

Please complete the following two questions:

$($a$)(8$ points$)$ Please design a $2-$approximation algorithm for the Traveling Salesman

Problem $($TSP$).$ Include the pseudo$-$code for your algorithm and provide a brief

justification for why your algorithm achieves a $2-$approximation ratio.

Hints: Begin by solving the Minimum Spanning Tree $($MST$)$ problem. Use the

MST solution as a basis to construct a solution for the TSP problem.

$($b$)(8$ points$)$ In the TSP problem, suppose you have access to an oracle algorithm

IsTSPShorterThan$($V$,$ d$,$ l$),$ which returns $$True$$ if there exists a TSP tour whose

total length is less than l$,$ and $$False$$ otherwise.

Please design an algorithm to solve the TSP problem that utilizes the oracle algorithm, IsTSPShorterThan$($V$,$ d$,$ l$),$ and ensures that the number of oracle calls is

O$($log n$).$ Include the pseudo$-$code for your algorithm and provide a brief justification for why your algorithm calls the oracle at most O$($log n$)$ times.

Hints: we can adopt a binary search strategy over the range of possible tour lengths.