cs215 ยป

The question requests that given a list of numbers

you calculate a value toTo get rid of the absolute value, we break the sum into two parts:

Let

be the number of elements in that are less then or equal to , and be the number of elements greater then . Then, the sum can be written:Note that

and don't depend on so we can ignore them. Minimizing the original function is equivalent to minimizing:is minimized when . This happens when is the median of .

Finding the median can be done in linear time using the Top K Partitioning Algorithm covered in lessons 16-18 of Unit 4.