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 0: Complete your self-assessment for Homework #3 for Problem 2 and at least one other problem (preferably one you feel less confident about). Use the Gradescope bubble sheet template. Scan and upload your completed bubble sheet to the Self-Assessment assignment on Gradescope when you are complete. (Credit will be given as long as you make a good faith effort, no matter how much your assessment and the graders' assessments differ.)

Problem : Linneapolis is built on the north bank of the Linninnippi River. Each building in Linneapolis is on the riverfront and, due to local architectural requirements, each is of a unique height.

We have a contract to install a 0.1G network in Linneapolis. Our plan is divided into phases: in the first phase we find all the buildings whose heights are local maxima (taller than its immediate neighbors both upstream and downstream). We then install radio links to connect each other (non-local-maximum) building to the closest local maximum in both the upstream and downstream directions as long as that closest local maximum is taller (and using a frequency that penetrates buildings so we don't have to worry about line of sight). This will connect all the buildings, but possibly with many connections required to get between two arbitrary buildings. So in the next phase, we find the local maxima of the local maxima (the local maxima from the first phase that are taller than the closest other 1st-phase local maximum both upstream and downstream) and connect the other local maxima to the closest local maximum of the local maxima both upstream and downstream. We repeat this process until only the global maximum is left.

• Prove that at each phase, if there are $n$ buildings at the beginning of the phase, we eliminate at least $\lfloor \frac{n}{2} \rfloor$ buildings.
• Describe an efficient algorithm to determine how many phases we need (we do not necessarily care about the actual links to construct for this problem). The input should be a list containing the heights of the buildings in order from upstream to downstream. State the asymptotic efficiency of your algorithm and explain that result.

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.)

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 and explain that result.

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 : Given any tree, we can root the tree by choosing an arbitrary vertex as the root. Each vertex $v$ aside from the root then has a parent: the first vertex on the unique simple path in the tree from $v$ to the root. The ancestor two levels up from $v$ is then $v$'s parent's parent. Its ancestor three levels up is its parent's parent's parent, and so on.

Describe an efficient algorithm that, given 1) a tree with vertices numbered $0, \ldots, n - 1$ represented using an adjacency list; and 2) the vertex selected as the root, computes $\pi[v, k]$ and $\mathop{max\_edge}[v, k]$ for all vertices $v$ and all integers $k$ such that $0 \le k \le \lfloor \log_2 n \rfloor$, where $\pi[v, k]$ is the ancestor $2^k$ levels up from $v$ (and $NIL$ if there is no such ancestor) and $\mathop{max\_edge}[v, k]$ is the weight of the maximum weight edge on the unique simple path from $v$ to $\mathop{\pi}[v, k]$ (and $\infty$ if there is no such ancestor).

Explain why your algorithm runs in $O(n \log n)$ time.