Q3 [15 Points] Dio's Student Life Dio, a U of T student, takes n courses this semester, each with a final course project due at exactly the same time. Each project will be graded on a scale from 1 to 100 . Dio wants to maximize the sum of the grades on the n course projects. Dio has a total of T hours to work on the n projects (Tn) and he wants to decide how to divide up this time. Assume that T is a positive integer, and that Dio will spend an integer number of hours on each project. Dio has come up with a set of functions f1(x),,fn(x) such that working x hours on project i will get him a grade of fi(x) on that project. Assume that fi(x) does not decrease if x increases, and fi(0)=0. Given T and f1(x),,fn(x), Dio needs to determine how many hours he will spend on each project so his sum of grades is as big as possible. (a) [5 Points] Let S[t,j] be the sum of the grades Dio will obtain by spending t hours in total on the projects for courses 1,2,,j. Write a Bellman equation for S[t,j], and explain why your Bellman equation is correct. (b) [7 Points] Using this Bellman equation, describe a dynamic programming algorithm that computes S[T,n]. Your algorithm should also return the amount of time you will spend on each course project. (c) [3 Points] Analyze the running time of your algorithm as a function of T and n