This is for an Introduction to Algorithms course, so no specific programming language should be used.

Please write the algorithm in general pseudocode and provide Proof of Correctness and Runtime Analysis.

Please show your work, and DO NOT use any pre-existing solutions to this question on Chegg Study.

You are given a rectangular piece of cloth with dimensions X XY, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i you know that a rectangle of cloth of dimensions ai x b is needed and that the selling price of the product is ci Assume the di, bi and C; are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that runs in time that is polynomial in X, Y, n and determines the best return on the X X Y piece of cloth, that is, a strategy for cutting the cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none, if desired. You are given a rectangular piece of cloth with dimensions X XY, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i you know that a rectangle of cloth of dimensions ai x b is needed and that the selling price of the product is ci Assume the di, bi and C; are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that runs in time that is polynomial in X, Y, n and determines the best return on the X X Y piece of cloth, that is, a strategy for cutting the cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none, if desired