Question

Suppose you are given n ropes of different lengths, you need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. You want to find the minimum cost way to do this. For example: Suppose you have three ropes with lengths 2, 5, and 8. If you chose first to connect the length 5 and 8 ropes, then connect the length 2 and 13 ropes, the total cost would be (5 + 8) + (13 + 2) = 28. However, if you first chose to connect the length 2 and 5 ropes, then the length 7 and 8 ropes, the total cost would be (2 + 5) + (7 + 8) = 22 (which happens to be optimal).

a)Specify with pseudo code a greedy algorithm to connect the ropes with minimum cost.

b)Prove you algorithm always finds the least cost solution if the lengths of the ropes are distinct.

c)Analyze your algorithms complexity

Answer 1

A)
Greedy based solution:
Algo to find the minimum cost for connecting n ropes.

Suppose we have n ropes in an array element as length = arr[n]

total_cost = 0
1) Create a min heap and insert all length in min heap.
2) Do following while number of elements in min heap is greater then 1.
   i) min1 = get minimum from min heap // smallest
   ii) min2 = get miniumum from min heap // second smallest
   iii) total_cost += min1 + min2
   iv) insert (min1 + min2) to min heap
3) return total_cost

B)

   main point to be noted here is, the lengths of the ropes which are selected first
   are included multiple times in calculating total cost.
   let r1 len(r1) = l1 and r2 len(r2) = l2 and l1 < l2 (distinct length)
   if we are merging rope r2 before r1, then l2 will be added multiple times let it be K times. so total cost C2 = K.l2 + X
   instead if we are merging rope r1, then total cost C1 = K.l1 + X
   since, l1 < l2
           K.l1 < K.l2
           k.l1 + X < k.l2 + X
           C1 < C2
   so, our approcah is optimal for distinct length

C)
   complexity:
   1) Create a min heap and insert all length in min heap.   O(n) // time taken to create heap
   2) Do following while number of elements in min heap is greater then 1. // n no of times
       i) min1 = get minimum from min heap // smallest O(lon n)
       ii) min2 = get miniumum from min heap // second smallest O(log n)
       iii) total_cost += min1 + min2 O(1)
       iv) insert (min1 + min2) to min heap O(log n)
   3) return total_cost O(1)
  
   total compeexity = nlogn