1. For all algorithms that you are asked to "give" or "design", you should Describe your algorithm clearly in English. Give pseudocode. Argue correctness. Give the best upper bound that you can for the running time. 2. If you give a Dynamic Programming algorithm, the above requirements are modified as follows: (a) Clearly define the subproblems in English. (b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an inductive proof of correctness too for practice but points will not be deducted if you don't). Then give the recurrence in symbols. (c) State boundary conditions. (d) Analyze time. (e) Analyze space. (f) If you're filling in a matrix, explain the order to fill in subproblems in English. (g) Give pseudocode. 4. (30 points) You are given a line L that represents a long hallway in an art gallery and a sorted set X = {21, 12,..., In} of real numbers that specify the positions of paintings in this hallway. Suppose that a guard can protect all the paintings within distance at most 1 of their position on both sides. Give an efficient algorithm that returns (a) the minimum number of guards to protect all the paintings; and (b) a placement of the guards that achieves this minimum number. 1. For all algorithms that you are asked to "give" or "design", you should Describe your algorithm clearly in English. Give pseudocode. Argue correctness. Give the best upper bound that you can for the running time. 2. If you give a Dynamic Programming algorithm, the above requirements are modified as follows: (a) Clearly define the subproblems in English. (b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an inductive proof of correctness too for practice but points will not be deducted if you don't). Then give the recurrence in symbols. (c) State boundary conditions. (d) Analyze time. (e) Analyze space. (f) If you're filling in a matrix, explain the order to fill in subproblems in English. (g) Give pseudocode. 4. (30 points) You are given a line L that represents a long hallway in an art gallery and a sorted set X = {21, 12,..., In} of real numbers that specify the positions of paintings in this hallway. Suppose that a guard can protect all the paintings within distance at most 1 of their position on both sides. Give an efficient algorithm that returns (a) the minimum number of guards to protect all the paintings; and (b) a placement of the guards that achieves this minimum number