There is a complete binary tree with its leaves as components of some systemThe values from one node to another gives propagation time for a signal to propagate from one junction to another For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires.The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.For example, one way to removeclock skew from the tree to the rightwould be to increase each edge so that ithas delay 6. This has cost 44. Second way is to raise the costsof all edges in the bottom layer to 6, alledges in the middle layer to 5, and alledges in the top layer to 4. This has cost36.One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the rootIs there any other way to get the best solution for minmizing cost to add delay??
Minimizing Cost by minimizing delay
algorithms;optimization;greedy algorithms
You can do a lot better than a total delay of 36. In fact you can get a total delay of half that. The idea is to recursively adjust the delays from bottom up.In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8. At the start, the component delays, reading from the left are:8, 11, 8, 12, 5, 5, 7, 10In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.After the first adjustments, the component delays are now11, 11, 12, 12, 5, 5, 10, 10Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.After the second adjustments the delays are12, 12, 12, 12, 10, 10, 10, 10Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync. So finally, the component delays are12, 12, 12, 12, 12, 12, 12, 12We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.