For problems that require you to provide an algorithm, you must give the

following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

3. The country of Ecolinearia has managed to find a method of recycling every single item that used to go to landfills. The last step in becoming a zero waste society is for the government to decide where to place k recycling plants. This is where you come in. There are n cities in Ecolinearia, and there is a completely straight central road that passes through all the cities. The cities have positions p,... .Pn, all of which can be considered to be integers, and you can assume that pl P2??Pn. The government has funds to build k