The rod-shipping problem is the following. Given a steel rod of n feet and a table of shipping costs c , for rods of size j = 1,2,..,n feet, determine the minimum total cost to ship the n foot rod by cutting it into smaller pieces and shipping the pieces. Assume that there is no cost associated with cutting the rod. Note that if the shipping cost c for a rod of size n is small enough, an optimal solution may require no cutting and shipping the n foot rod intact.

(a) What algorithm paradigm is most appropriate for this problem? Divide - and - conquer, Greedy algorithm, Dynamic Programming, Brute Force, Enumeration or None of these

(b) Verbally describe and give pseudo-code for an efficient algorithm to solve this problem.

(c) What is the asymptotic running time of your algorithm? Explain.