Moonbucks Coffee Shops are planning to open up new shops along a major street in San Francisco. The street has n intersections numbered consecutively from 1 to n as you travel from North to South. Each intersection i has a projected profit of p[i] that can be earned by placing a shop at that intersection. The city law prohibits Moonbucks coffee shops to be placed at adjacent intersections. The input to the problem is the number of intersections n and the array of projected profits p[1,...,n]. Our ultimate goal is to determine a list L of intersections where Moonbucks should open up shops to maximize the total profit Lier pi). To that end, define a table C[1,..., n] such that C[j] is the maximum profit possible from the first j intersections (i.e., intersections 1 through j). (a) Specify a recurrence (including any base cases) to fill the table C defined above. Also, explain your recurrence. The explanation needn't be lengthy, but should make clear, in English, how you arrived at the base case(s) and also the general case. [8 points] Hint: similarly to a problem we studied, the general case of the recurrence involves a "binary choice" (solutions with and without the jth intersection). (b) Describe* an algorithm which efficiently (using dynamic-programming) solves the problem by using the recurrence you found in (a) to fill the table C. State any assumptions you make. [8 points] (c) Give the running time requirement for your algorithm, as a Theta...) expression, and justify it (i.e., explain in English). [4 points] * The algorithm description for (b) can be pseudocode, English descriptions, or something in between. The priority is clarity: make it clear how, and in what order, the elements of C will be determined. Moonbucks Coffee Shops are planning to open up new shops along a major street in San Francisco. The street has n intersections numbered consecutively from 1 to n as you travel from North to South. Each intersection i has a projected profit of p[i] that can be earned by placing a shop at that intersection. The city law prohibits Moonbucks coffee shops to be placed at adjacent intersections. The input to the problem is the number of intersections n and the array of projected profits p[1,...,n]. Our ultimate goal is to determine a list L of intersections where Moonbucks should open up shops to maximize the total profit Lier pi). To that end, define a table C[1,..., n] such that C[j] is the maximum profit possible from the first j intersections (i.e., intersections 1 through j). (a) Specify a recurrence (including any base cases) to fill the table C defined above. Also, explain your recurrence. The explanation needn't be lengthy, but should make clear, in English, how you arrived at the base case(s) and also the general case. [8 points] Hint: similarly to a problem we studied, the general case of the recurrence involves a "binary choice" (solutions with and without the jth intersection). (b) Describe* an algorithm which efficiently (using dynamic-programming) solves the problem by using the recurrence you found in (a) to fill the table C. State any assumptions you make. [8 points] (c) Give the running time requirement for your algorithm, as a Theta...) expression, and justify it (i.e., explain in English). [4 points] * The algorithm description for (b) can be pseudocode, English descriptions, or something in between. The priority is clarity: make it clear how, and in what order, the elements of C will be determined
