Instructions:

Typically, the clearest way to explain an algorithm is in English, with the use of some notation. A clear explanation followed by annotated pseudo-code is also fine.

Remember that when a problem asks you to design an algorithm, you must also prove the algorithms correctness and analyze its running time, i.e., the running time must be bounded by a polynomial function of the input size.

(1) (10 points) There are n ropes and your task is to tie them into a single rope. The i 'th rope is of length i (for i=1,,n ). When you tie two rope segments, they become joined into one rope segment and you pay a cost equal to the sum of their lengths. Design an efficient algorithm to find a sequence of joining operations that combines the n ropes into a single rope that minimizes the combined cost. Your algorithm should output the sequence of operations, and the minimum cost. Example: Suppose you have ropes A, B, C, D, E with lengths 2, 4, 5,3,8 respectively, and that you join B and C into segment BC with length 9 , then you join D and E into segment DE with length 11 , then you join A with BC to form ABC with length 11, and finally you join ABC to DE to form a rope of length 22 containing all of the segments. Then the total cost would be 9+11+11+22=53. The process of joining the segments can be represented pictorially by a binary tree, as illustrated in Figure 2. Figure 1: Binary tree corresponding to the example discussed. The internal nodes are labelled by the lengths of the segments to which they correspond