Exercise $4.$ How to PASS THE MIDTERM.

$[18$ points$]$

Consider an exam with $\backslash ($ n $\backslash )$ questions, each worth $\backslash ($ v$[$i$]\backslash )$ points and requiring $\backslash ($ t$[$i$]\backslash )$ minutes to solve.

Your goal is to pass the exam with the minimum possible effort. Write an algorithm that, given arrays $\backslash ($ v$[1,\backslash$ldots$,$ n$],$ t$[1,\backslash$ldots$,$ n$]\backslash ),$ and a threshold $\backslash ($ V $\backslash )$ representing the passing score, finds the subset of questions requiring the least time to achieve the passing score.

$($a$)(4$ points$)$ Let $\backslash ($ T$($i$,$ v$)\backslash )$ be the minimum time required to score at least $\backslash ($ v $\backslash )$ points by solving any subset of the first $\backslash ($ i $\backslash )$ problems. Write a recursive expression for $\backslash ($ T$($i$,$ v$)\backslash ).$

$($b$)(8$ points$)$ Write the algorithm based on dynamic programming.

$($c$)(2$ points$)$ Analyze the complexity of the proposed algorithm. Justify briefly.

$($d$)(4$ points$)$ Now, suppose that solving a problem partially can yield a proportionate score $($e$.$g$.,$ solving $\backslash ($ x $\backslash \%\backslash )$ of a problem gives you $\backslash ($ x $\backslash \%\backslash )$ of the points$).$ Describe an $\backslash ($ O$($n $\backslash$log n$)\backslash )$ algorithm to solve the same problem.