Code must be written in C Language/ UBUNTU environment.

To get full credit for each question, you need to provide a brief explanation of your codes and the efficiency analysis with comments.

1. Assume there is a bus company serving along a highway with m km and there are n people using this company for travel. They all board the bus at the starting point 0, and each passenger i specifies a destination x; for the travel before boarding(x; here indicates the distance from the destination to the starting point). If the passenger i leaves the bus at a position y, then the unhappiness of the passenger i will be (xi - y)2. There are no fixed bus stops. All the stops will be determined after gathering the destinations from all the passingers, and the bus can make at most k stops. Devise a dynamic programming algorithm that takes n destinations X, ... , Xn and an integer k as input, and outputs an optimal set of positions for k stops that minimizes the sum of the unhappiness of all the passengers. Note that all the inputs given to the algorithm are assumed to be integers and the x; values are given as sorted in increasing order