Notes:

• For this class is is generally not necessary to validate input in your pseudocode: if a problem says the input will be in a certain form then write your pseudocode under the assumption that the input is in that form.
• "Find/devise/give an efficient algorithm" means "find an algorithm that is as efficient as possible, and you have to figure out for yourself whether your solution can be improved."

Problem : Consider the process of fabricating carbon-fiber-reinforced titanium-magnesium rods for use in the vibrant rod arranging hobbyist community. The tool to cut these rods is very expensive, so they can only be cut at the factory, not in the field. As a result, differing demand for different length rods may result in the value of a rod of one length being greater than the value of a rod of a longer length. (This is not true for other materials that can be cut in the field: a 12' walnut board will certainly cost more, and possibly much more, than a 4' walnut board.)

At the factory, though, a rod of a given length may be cut and recut into many pieces. Each cut costs $m$ units of value, and wastes 1 unit of length (think sawdust). Both ends must be secured as a rod is cut, so it is impossible to cut at the very end of a rod – any cut must leave at least 1 unit on each side of the cut.

Devise an efficient algorithm for determining the maximum net value over all possible ways to cut and recut a rod, given the initial integer length $n$, the cost per cut $m$, and the values $v_1, \ldots, v_n$ for any positive integer length up to and including $n$ (assume that non-integer lengths are worthless). State the running time of your algorithm.

For example, if the values for lengths of 1 to 6 are $[8, 3, 12, 8, 4, 1]$ and $m=6$ then a best plan for a rod of length 6 is to cut it into pieces of length 1 and 4 for a net value of $8 + 8 - 6 = 10$ but with the same values and $m=1$ a best plan is to cut the rod into lengths of 2 and 3 and then further cut the length of 3 into two lengths of 1 for a net value of $3 + 8 + 8 - 2 = 17$.

Problem : Generalize the vendor scheduling problem to $k$ cities: given values $p_{ij}$ that represent the profit obtained by selling cut-rod arrangements in city $i$ during week $j$, and the cost of moving from city to city $m$, which is the same no matter what city you move from and to, determine an optimal schedule and its net profit in $O(nk)$ time.

Problem : Devise an $O(n \log n)$ algorithm that, given an array of integers $A$, for each element determines the number of elements that come after it in the array that are strictly less than it. The output should be an array $C$ so that $C[i]$ is the number of elements in $A[i+1], \ldots, A[n]$ that are strictly less than $A[i]$. So if $A = [3, 5, 2, 1, 4]$ then the output should be $[2, 3, 1, 0, 0]$.

Problem : Tardos and Kleinberg, Ch. 5, Ex. 7 You needn't prove that your algorithm is correct, but you should explain why the runtime is $O(n)$ (Hint: try Ex. 6 first and modify your approach for the grid.)