CS215 Unit 4 Solutions

CS215 Unit 4 Solutions: Mean

Thanks to ked4r for his post on solving this problem without calculus (http://forums.udacity.com/cs215/questions/3277/spoilers-mathematical-proofs-for-ps4-2-and-ps4-3/3296):

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

Expanding the square, we get: \begin{align} \sum^{n-1}_{i=0}{(L[i] - x)^2} &= \sum_{i=0}^{n-1}{x^2 - 2 x L[i] + L[i]^2}\\ &= nx^2 - 2 x \sum_{i=0}^{n-1}L[i] + \sum_{i=0}^{n-1}L[i]^2 \end{align}

Note that \sum_{i=0}^{n-1}L[i]^2 does not depend on x so equation \eqref{eq:min} is equivalent to calculating

$$\label{eq:smallmin}\tag{2} \min\left(nx^2 - 2 x \sum_{i=0}^{n-1}L[i]\right).$$

Let \sum_{i=0}^{n-1}L[i] = n k.  Then we can write

\begin{align} nx^2 - 2 x \sum_{i=0}^{n-1}L[i] &= nx^2 - 2 x n k \\ &= n (x^2 - 2 x k) \end{align}

We can then add and subtract k^2, which completes the square.

\begin{align} n (x^2 - 2 x k) &= n (x^2 - 2 x k + k^2 - k^2) \\ &= n ((x - k)^2 - k^2) \end{align}

Again, note that k^2 doesn't depend on x, and that \min((x - k)^2) = 0.  This implies that Equation \eqref{eq:smallmin} is minimized when x = k and k = \frac{\sum_{i=0}^{n-1}L[i]}{n}, which is the mean of L.

Calculating the mean of L in constant time can be done in one pass through the list, keeping track of the sum of elements seen so far along with a count.  In python you can also do sum(L)/len(L).