2
$\begingroup$

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 &= \{2, 3, 5\} \\ S_1 &= \{5, 5\} \\ S_2 &= \{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$.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.