4. The traveling salesman problem is one of the hardest problems of practical significance, and the best algorithm is therefore suspected to take more than polynomial time. No wonder that people have considered many simplified variants. One such a variant is the euclidean traveling salesman problem, where the vertices of the graph are points on a plane (therefore being defined by their x- and y-coordinates) and the distance between two vertices is the Euclidean distance between the respective points. It turns out that this variant is just as hard as the original problem. People have suggested a further simplification by only considering bitonic tours that is, tours that start at the leftmost point (smallest x-coordinate), go strictly to the right until they reach the rightmost point (with the largest x-coordinate), and then go strictly to the left back to the initial point. Design an O(n²)-time algorithm for finding an optimal bitonic tour. You may assume that no two points have the same x-coordinate. Note that there is no substantial difference between the two parts of the tour, and so you may want to scan left to right, maintaining optimal possibilities for these two parts.

4. The traveling salesman problem is one of the hardest problems of practical significance, and the best algorithm is therefore suspected to take more than polynomial time. No wonder that people have considered many simplified variants. One such a variant is the euclidean traveling salesman problem, where the vertices of the graph are points on a plane (therefore being defined by their x- and y-coordinates) and the distance between two vertices is the Euclidean distance between the respective points. It turns out that this variant is just as hard as the original problem. People have suggested a further simplification by only considering bitonic tours that is, tours that start at the leftmost point (smallest x-coordinate), go strictly to the right until they reach the rightmost point (with the largest x-coordinate), and then go strictly to the left back to the initial point. Design an O(n²)-time algorithm for finding an optimal bitonic tour. You may assume that no two points have the same x-coordinate. Note that there is no substantial difference between the two parts of the tour, and so you may want to scan left to right, maintaining optimal possibilities for these two parts.