Provide the proof of correctness and time complexity.

Problem 2 (25 points). You are given a set of n ropes of different lengths {li,..., ). You are supposed to tie these ropes into a single rope. The cost of joining two ropes equals the sum of the lengths of the two ropes, ie. C = lit , Design an algorithm that will incur the total minimum cost, and prove its optimality. For the algorithm, think of what happens to the set of ropes after you've made a join. For your proof, think of the greedy stays ahead strategy Example: If you have 4 ropes of lengths: 4,3,2,6], the optimal strategy is the follow ing: Connect 2 and 3 C 5. Now you have three ropes of lengths {4,5,6} Connect 4 and 5 C = 9. The remaining ropes are 19,6) Connect 9 and 6 C = 15 Total cost: 5 + 9 + 15 29