Marking Scheme (for both questions): Program is correct and must use greedy (8 points) Program is correct but does not use greedy 4 points Program is correct, uses greedy, but fails on few testing cases 4 points Program is correct, uses greedy, but fails on many testing cases 2 points Program does not run, or fails on most testing cases 1 point Program has the required efficiency (8 points) Program only fails on few test cases but meets the efficiency 6 points Program is correct but slightly inefficient 3 points Program is correct but significantly inefficient 1 point Pseudocode is in plain English and is a clear description of your algorithm (3 points) Using only slightly modified Python program for pseudocode 1 point Parameters, return, and function name are as specified (2 points) Program style and logic are clear and concise (2 points) Explanation on the complexity of the algorithm is clear (1 point) Comments are appropriate and program is easy to understand (1 point) Note: Calling Python functions/methods on a list costs a certain complexity. For instance, len() takes constant time, sort( takes O(n log n) time, max( ), min( ), or sum() takes O(n) time. T3_2 (25 Marks) Minimum Lamps: City of Kingston has set up new lamp posts on Ontario street. They start at the City Hall (position 0) and extends to the intersection of Ontario and Earl (position n). The total length of this section of street is n. There are n + 1 equally spaced lamp posts located at positions 0, 1, 2, ..., n on the street. Each lamp post has its own illumination capacity, measured using radius r[i]. The i-th lamp post can illuminate the area [i r[i], i +r[i]] if it is turned on. A radius is a non-negative integer. A radius of 0 means the lamp is out of work. r[0] = 2 r[3] = 3 0 1 2 3 n Provide an algorithm with O(n log n) complexity to illuminate the entire street section by turning on the minimum number of lamps. Write a function min_lamp(r) that inputs a list r of radiuses and returns the minimum set of indices of lamp posts that can be turned on to illuminate the entire street section [0, n], wheren= |r1 1. If such a solution cannot be found, return None. For example, min_lamp([1, 1, 2]) returns [2], meaning turning on as few as one lamp at position 2 min_lamp([0,0,1,1,0,2]) returns None min_lamp([2, 2, 1, 1, 1, 3]) returns [1, 5] Marking Scheme (for both questions): Program is correct and must use greedy (8 points) Program is correct but does not use greedy 4 points Program is correct, uses greedy, but fails on few testing cases 4 points Program is correct, uses greedy, but fails on many testing cases 2 points Program does not run, or fails on most testing cases 1 point Program has the required efficiency (8 points) Program only fails on few test cases but meets the efficiency 6 points Program is correct but slightly inefficient 3 points Program is correct but significantly inefficient 1 point Pseudocode is in plain English and is a clear description of your algorithm (3 points) Using only slightly modified Python program for pseudocode 1 point Parameters, return, and function name are as specified (2 points) Program style and logic are clear and concise (2 points) Explanation on the complexity of the algorithm is clear (1 point) Comments are appropriate and program is easy to understand (1 point) Note: Calling Python functions/methods on a list costs a certain complexity. For instance, len() takes constant time, sort( takes O(n log n) time, max( ), min( ), or sum() takes O(n) time. T3_2 (25 Marks) Minimum Lamps: City of Kingston has set up new lamp posts on Ontario street. They start at the City Hall (position 0) and extends to the intersection of Ontario and Earl (position n). The total length of this section of street is n. There are n + 1 equally spaced lamp posts located at positions 0, 1, 2, ..., n on the street. Each lamp post has its own illumination capacity, measured using radius r[i]. The i-th lamp post can illuminate the area [i r[i], i +r[i]] if it is turned on. A radius is a non-negative integer. A radius of 0 means the lamp is out of work. r[0] = 2 r[3] = 3 0 1 2 3 n Provide an algorithm with O(n log n) complexity to illuminate the entire street section by turning on the minimum number of lamps. Write a function min_lamp(r) that inputs a list r of radiuses and returns the minimum set of indices of lamp posts that can be turned on to illuminate the entire street section [0, n], wheren= |r1 1. If such a solution cannot be found, return None. For example, min_lamp([1, 1, 2]) returns [2], meaning turning on as few as one lamp at position 2 min_lamp([0,0,1,1,0,2]) returns None min_lamp([2, 2, 1, 1, 1, 3]) returns [1, 5]