5 (**) Steel Beams You're a construction engineer tasked with building a new transit center for a large city. The design for the center calls for a T-foot-long steel beam for integer T > 0. Your supplier can provide you with an unlimited number of steel beams of integer lengths 0C1 ck feet. You can weld as many beams as you like together; if you weld together an a-foot beam and a b-foot beam you'l have an (a b)-foot beam. Unfortunately, every weld increases the chance that the beam might break, so you want as few as possible Your task is to design an algorithm which outputs how many beams of each length you need to obtain a T-foot beam with the minimum number of welds, or 'not possible' if there's no way to make a T-foot beam from the lengths you're given. (If there are multiple optimal solutions, your algorithm may return any of them.) (a) Consider the following greedy strategy. Start with zero beams of each type. While the total length of all the beams you have is less than T, add the longest beam you can without the total length going over T (i) Suppose that we have 1-foot, 2-foot and 5-foot beams. Show that the greedy strat- (ii) Find a (short) list of beam sizes ci,... , ck and target T such that the greedy strategy (b) Give a dynamic programming algorithm which always finds the optimum. Describe your egy always finds the optimum fails to find the optimum. Briefly justify your choice. algorithm, including a clear statement of your recurrence, show that it is correct and prove its running time. How much space does your algorithm use? 5 (**) Steel Beams You're a construction engineer tasked with building a new transit center for a large city. The design for the center calls for a T-foot-long steel beam for integer T > 0. Your supplier can provide you with an unlimited number of steel beams of integer lengths 0C1 ck feet. You can weld as many beams as you like together; if you weld together an a-foot beam and a b-foot beam you'l have an (a b)-foot beam. Unfortunately, every weld increases the chance that the beam might break, so you want as few as possible Your task is to design an algorithm which outputs how many beams of each length you need to obtain a T-foot beam with the minimum number of welds, or 'not possible' if there's no way to make a T-foot beam from the lengths you're given. (If there are multiple optimal solutions, your algorithm may return any of them.) (a) Consider the following greedy strategy. Start with zero beams of each type. While the total length of all the beams you have is less than T, add the longest beam you can without the total length going over T (i) Suppose that we have 1-foot, 2-foot and 5-foot beams. Show that the greedy strat- (ii) Find a (short) list of beam sizes ci,... , ck and target T such that the greedy strategy (b) Give a dynamic programming algorithm which always finds the optimum. Describe your egy always finds the optimum fails to find the optimum. Briefly justify your choice. algorithm, including a clear statement of your recurrence, show that it is correct and prove its running time. How much space does your algorithm use