Suppose you are the postmaster in charge of putting a new post office in a small town, where all ... Suppose you are the postmaster in charge of putting a new post office in a small town, where all the houses are along one street, where the new post office should go as well. Let us view this street as a line and the houses on it as a set of real numbers, {x1, x2, . . . , xn}, corresponding to points on this line. To make everyone in town as happy as possible, the location, p, for the new post office should minimize the sum,

Describe an efficient algorithm for finding the optimal location for the new post office, show that your algorithm is correct, and analyze its running time.

p- i 1