cs215 ยป

CS215 Unit 4 Solutions

CS215 Unit 4 Solutions: Median

The question requests that given a list of numbers L you calculate a value x to \min\left(\sum^{n-1}_{i=0}{|L[i] - x|}\right).

To get rid of the absolute value, we break the sum into two parts: \sum^{n-1}_{i=0}{|L[i] - x|} = \sum_{L[i]<=x}{(x - L[i])} + \sum_{L[i]>x}{(L[i] - x)}.

Let k_1 be the number of elements in L that are less then or equal to x, and k_2 be the number of elements greater then x.  Then, the sum can be written: \sum_{L[i]<=x}{(x - L[i])} + \sum_{L[i]>x}{(L[i] - x)} = k_1 x - \sum_{L[i]<=x}{L[i]} + \sum_{L[i]>x}{L[i]} - k_2 x

Note that \sum_{L[i]<=x}{L[i]} and \sum_{L[i]>x}{L[i]} don't depend on x so we can ignore them.  Minimizing the original function is equivalent to minimizing: \min(\sum^{n-1}_{i=0}{|L[i] - x|}) \Rightarrow \min(k_1 x - k_2 x)

k_1 x - k_2 x is minimized when k_1 = k_2.  This happens when x is the median of L.

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