$($a$)$ Suppose you are given an array A$[1..$ n$]$ of numbers. What is the fastest running

time we saw for finding the $$n$/4$th smallest number in A$?$

$($b$)$ Let X$[1..$ n$,1..$n$]$ be a $2$D array of numbers. Consider the function Boing$($i$,$ j$)$

defined recursively as follows:

Boing$($i$,$ j$)=$

$0$ if i $>$ n or j $<1$

X$[$i$,$ j$]+$ max $\{$Boing$($i $+1,$ j$),$Boing$($i$,$ j $1)\}$ otherwise

In terms of n$,$ how long does it take to compute Boing$(1,$ n$)$ using dynamic programming?

$($c$)$ Suppose you are given a directed acyclic graph G $=($V$,$ E$)$ and you compute a

postorder of its vertices using DFSAll$($G$).$ What is special about the reversal of this

postorder?

$($d$)$ Suppose you are given an undirected graph G $=($V$,$ E$)$ with distinct real edge

weights w : E $$ R$.$ You can find the minimum spanning tree of G using Kruskal$$s

algorithm. It consists of two phases, sorting the edges by weight and scanning the

edges whereby you add each edge that doesn$$t create a cycle to the intermediate

spanning forest.

Assuming use of a good union$-$find data structure and comparison$-$based sorting

algorithm, which of the two phases has a larger worst case running time?

$($e$)$ Let G $=($V$,$ E$)$ with s$,$ t in V be a flow network with non$-$negative edge capacities

c : E $$ R$0$

$.$ Let f be a maximum value feasible $($s$,$ t$)-$flow, and let $($S$,$ T$)$ be a

minimum capacity $($s$,$ t$)-$cut. What must be true about f $($uw$)$ for each u in S and

w in T$?$ This is a practice exam question my professor gave me$.$ Could you help me solve these problems with only logic, no code.