1. a precise description of the algorithm and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

4. You are a humble process scheduler on an algorithm student's laptop, and it's your job to handle what problems the CPU is crunching on at any given time. Unfortunately, your user likes to kick off multiple big problems at once, and then keep browsing the web while they run, so you have to figure out how to not only change with varying processing conditions, but also how to optimally switch back and forth between the different problems so that they all finish as soon as possible. Today, luckily, you only have two problems to deal with. Given the two problems P and Q, you know that, at any given cycle i (i ranges from 1 to n), the CPU can do pi work on problem P or qi work on problem Q. Additionally, switching problems takes 100 consecutive cycles. as input.(Note that these numbers should be non- Fornally, yol re given pi .. Pn and q1 . - In negative.) A plan is an assignment of "work on P", "work on Q" or "switch jobs" to each of the n cycles. You goal is to design a dynamic programming algorithm that creates a plan such that you maximize ET,, Pi + TOVi where Tp and To are the cycles spent working on P and Q respectively. hat are the subproblems that your algorithm will iteratively solve (b) Give a recursive formula for these subproblems in terms of pi's, qi's and other subproblem solutions. Justify these briefly, and explicitly include your base cases. (c) Briefly describe your algorithm for designing the plan. Use psuedocode if necessary. (d) Give a brief analysis of your algorithm's time and space complexity. 4. You are a humble process scheduler on an algorithm student's laptop, and it's your job to handle what problems the CPU is crunching on at any given time. Unfortunately, your user likes to kick off multiple big problems at once, and then keep browsing the web while they run, so you have to figure out how to not only change with varying processing conditions, but also how to optimally switch back and forth between the different problems so that they all finish as soon as possible. Today, luckily, you only have two problems to deal with. Given the two problems P and Q, you know that, at any given cycle i (i ranges from 1 to n), the CPU can do pi work on problem P or qi work on problem Q. Additionally, switching problems takes 100 consecutive cycles. as input.(Note that these numbers should be non- Fornally, yol re given pi .. Pn and q1 . - In negative.) A plan is an assignment of "work on P", "work on Q" or "switch jobs" to each of the n cycles. You goal is to design a dynamic programming algorithm that creates a plan such that you maximize ET,, Pi + TOVi where Tp and To are the cycles spent working on P and Q respectively. hat are the subproblems that your algorithm will iteratively solve (b) Give a recursive formula for these subproblems in terms of pi's, qi's and other subproblem solutions. Justify these briefly, and explicitly include your base cases. (c) Briefly describe your algorithm for designing the plan. Use psuedocode if necessary. (d) Give a brief analysis of your algorithm's time and space complexity