You are designing a flight scheduler for an airline AlgorithmAir. You will have access to a list of daily

flights, $F_{1}dots{F}_n,$ each with a departure airport, departure time, arrival airport, arrival time, and cost,

$F_i=(D{A}_i,D{T}_i,A{A}_i,A{T}_i,c_i).($Times are measured in minutes after midnight UTC time.$)$

A passenger can make a flight connection from $(D{A}_i,D{T}_i,A{A}_i,A{T}_i,c_i)$ to $(D{A}_j,D{T}_j,A{A}_j,A{T}_j,c_j)$ if

and only if $A{A}_i==D{A}_j.$ This connection will have a total layover time of $D{T}_j-A{T}_i$ if $24-(A{T}_i-D{T}_j)D{T}_{j}A{T}_{i}jn\{F_1,$dots,$F_n\}DADADAn{F}_{1}dots{F}_{n}k{P}_1,$dots,$P_{k}DAn{F}_1,$dots,$F_{n}k{P}_1,$dots,$P_{n}DA{P}_i{P}_{i}DAA{T}_i$

$or24-(A{T}_i-D{T}_j)ifD{T}_{j}A{T}_i,i.e.,$ the passenger will have $to$ wait until the next day $to$ take flight

$j.$

$(a)$ Given a list $ofn$ available daily flights $\{F_1,$dots,$F_n\},$ a departure airport $D$ and $an$ arrival airport $A,$

design $an$ algorithm that returns the minimum cumulative layover time among all valid sequences

$of$ flights starting from airport $D$ and ending $at$ airport $A.(You$ can ignore cost for this question.$)$

$(7$ points for reasonably efficient correct high level algorithm description $(with$ correctness proof$),$

$5$ points for correct time analysis, and $3$ points for efficiency $of$ your algorithm.$)$

$(b)$ You notice that the route from $DtoAis$ very popular and you want $to$ make that particular

route cheaper than $itis.$ There are $n$ available daily flights $F_{1}dots{F}_n$ that are already running.

There are $k$ potential future flights $P_1,$dots,$P_k$ that the airline $is$ considering $to$ add. You wish

$to$ find exactly one $of$ the potential future flights $to$ make available that will result $in$ the cheapest

sequence $of$ flights from $DtoA.$

Given a list $ofn$ available daily flights $F_1,$dots,$F_n$ and list $ofk$ potential future daily flights

$P_1,$dots,$P_n$ and a departure airport $D$ and arrival airport $A,$ design $an$ algorithm that returns

the index $of$ the potential future daily flight $P_i$ such that $if{P}_{i}is$ included $in$ the list $of$ available

flights, $it$ will result $in$ the minimum cost among all valid sequences $of$ flights from $DtoA.$

$(7$ points for reasonably efficient correct high level algorithm description $(with$ correctness proof$),$

$5$ points for correct time analysis, and $3$ points for efficiency $of$ your algorithm.$)$