How do I minimize the cost of some algorithm that performs some operation on a list? I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem precisely). The "hint" is more of a conjecture which I can't prove than a hint.

Let $S_0 = \{s^0_1, ..., s^0_n\}$ be a list containing $n$ positive integers. Let $k$ be the length of $S_{i - 1}$, and define $S_1, ..., S_{n - 1}$ recursively as follows: choose $1 \leq r, s \leq k, \quad r \neq s$, and define 
       \begin{equation*}
       S_i := (S_{i - 1} \setminus (\{s^{i - 1}_r\} \cup \{s^{i - 1}_s\})) \cup \{s^{i - 1}_r + s^{i - 1}_s\}
   \end{equation*}
       E. g.
       \begin{align*}
       S_0 &amp;= \{2, 3, 5\} \\
       S_1 &amp;= \{5, 5\} \\
       S_2 &amp;= \{10\}
   \end{align*}
       Clearly, $S_{n - 1}$ has a single element. Also, define $W_i := s^{i - 1}_r + s^{i - 1}_s$. Consider the quantity $\sum_{i = 1}^{n - 1} W_i$. In the previous example, this quantity can be $15$ or $18$. How do you have to choose $r$ and $s$ in each step so that $\sum_{i = 1}^{n - 1} W_i$ is minimal?

(Hint: Pick $r, s$ such that $s^{i - 1}_r = \min_{x \in S} x$, and $s^{i - 1}_s = \min_{y \in S \setminus \{x\}} y$.)
First, let us understand in more simple terms what you are trying to do. You start with a list of $n$ integers. Then you are repeating $n-1$ times the following operation: take a pair of integers, and replace them with their sum; this costs you the value of the sum. The costs accumulate additively, and your goal is to minimize the total cost.

You can construct a tree from the $n-1$ steps, in the following way. You start with $n$ isolated nodes. When adding two integers, you join them to a new root which represents their sum. In the end, you will have a binary tree whose leaves are the $n$ original integers. You can check that the total cost is $\sum_i d_i x_i$, where $x_i$ is the $i$'th integer and $d_i$ is its depth in the tree (number of edges from root to leaf). (A cost of $x_i$ is incurred each time that you add an integer in whose product $x_i$ was involved.)

At this point we have exactly reached the problem solved by Huffman's algorithm, which is exactly the algorithm given by your hint. You can look up a proof of optimality in many sources.