Problem : Suppose a restaurant sells orders of pierogies in distinct positive integer sizes $s_1, \ldots, s_k$ with positive costs $c_1, \ldots, c_k$.

• Give an algorithm that runs in $O(nk)$ time and $O(n)$ space and determines the minimum cost to order exactly $n$ pierogies total. (For example, if Yocco's sells pierogies in orders of size 1, 3, or 10 with corresponding costs 90 cents, $1.80, and $6.20 then the best way to order 11 pierogies total is to get a 1-pierogy order and a 10-pierogy order for a total cost of $7.10).
• Give an algorithm that runs in $O(nk)$ time and, given the original inputs plus an array $OPT$ containing the minimum cost to order $i$ pierogies total for $i=0, \ldots, n$, returns a list of the sizes of orders used to get $n$ pierogies while minimizing the total cost. For example, in the above example a list returned could be $[1, 10]$.

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 : A sorted graph is a directed graph with vertices $0, \ldots, n-1$ in which all of the edges go from lower-numbered vertices to higher-numbered vertices. Devise an efficient algorithm for determining the average path length of all the distinct paths from $0$ to $n-1$ in an ordered graph, or NaN if there are no paths from $0$ to $n-1$. State your algorithm's running time.

For example, in a graph with edges $(0, 1), (0, 2), (0, 3), (1, 2), (2, 3), (2, 4), (3, 4)$ the average path length from $0$ to $4$ is $\frac{14}{5}$ because the five paths from $0$ to $4$ are $01234, 0124, 0234, 024, 034$ and have total length 14.

---