Problem $11-5($Reaching Far and High$)11$ points

You are in charge of the Farther and Higher Mountain Guides company. The company owns $n$ guest houses: one at NYC$\text{'}$s Battery Park, and others at various locations in the Catskills. Each guest house #$i$ is at some altitude $h_i$ above sea level; all the heights are distinct numbers, and

satisfy $h_{i}0.$ A valid guided tour starts at the Battery Park guest house #$1($which is at sea$-$level, i$.$e$.,h_1=0),$ and involves spending exactly one day each at some subset of guest houses, such that each guest house in the sequence is $($a$)$ at a higher altitude than the previous guest house, and $($b$)$ strictly further away from the starting guest house. You charge ci $>=0$ for a day at guest house i$,$ so you want to find a valid path that maximizes the total amount you charge the client. We now develop an algorithm to find such a path in O$($n$^2)$ time.

$($a$)(2$ points$)$ Model the problem as finding a maximum$-$weight path in a directed acyclic graph $($DAG$)$ with vertex weights. Make sure you argue that the graph has no directed cycles.

$($b$)(5$ points$)$ Give an algorithm to find the maximum$-$weight path in a DAG G $=($V$,$ E$)$ with m directed edges and n vertices. Your algorithm should run in O$($m $+$ n$)$ time.

Note: you should return the maximum$-$weight path, and not just its length. Clearly indicate where you are using the acyclic property of the graph. $($Hint: use a graph algorithm you have seen in lecture, followed by dynamic programming.$)$

$($c$)(1$ point$)$ Now we want to count the total number of directed paths in a DAG. $($A single vertex also counts as a path. And the weights are no longer relevant.$)$ So$,$ for instance, if the graph G consisted of edges $\{($v$1,$ v$2),($v$2,$ v$3),...,($vn$1,$ vn$),$ show that the number of directed paths in G is n$($n$+1)/2.$

$($d$)(3$ points$)$ Now give an algorithm to output the total number of directed paths in a DAG. Again, show how to do this in time O$($n$2).($You don$$t need to use any ideas from part $($c$),$ but be sure to check your algorithm on the example there.$)$