Q.4. A professor in mathematics is coming to Singapore to attend an international conference. He plans to take a one-day tour of the Singapore after the three-day conference is over. Due to time constraint, he wants to find out the best route to see all the major attractions such as Sentosa Island, Singapore Flyer, Singapore Zoo etc. He stays at Marina Bay Sands hotel. So he will leave the hotel in the morning and comes back to hotel at night.To save time, he will take taxi from one place to another. What is the best route such that the traveling time on the road is the shortest?To plan the best path, the professor already knows the following:1. There are total of n major attractions he wishes to visit.2. The average traveling time from one major attraction to another (including the hotel) is known. To make it simpler, it is assumed that the average traveling time is the same for both directions for two fixed places. Can you help the professor to find out the best route? If n is not large, you can do it withbrutal force (exhaustive search) by listing out all the possible combinations. But since youare taking EE5110, you are expected to find a smarter solution with dynamic programming.