Graded Problem
A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The houses are labeled 1,2,…, n and the thief will address them sequentially. The thief has an estimate of the profit to be earned from burglarizing each house , where . To avoid detection, he decides that he will never burglarize two adjacent houses, meaning that if he burglarize house 2, he cannot burglarize house 1 or house 3. Design a dynamic programming algorithm to determine the maximum total profit he can achieve.
Example: In each of the following two neighborhoods, the maximum achievable profit is 100:
Case 1: p = [20, 100, 30].
Case 2: p = [40, 30, 10, 60].
Your input is the list . Your output should be the maximum profit the thief can get. You don’t have to return the list of houses the thief has to burglarize to achieve the maximum.
Please answer the following parts:
Define the entries of your table in words. E.g. T(i) or T(i, j) is …
State a recurrence for the entries of your table in terms of smaller subproblems. Don’t forget your base case(s).
Write pseudocode for your algorithm to solve this problem.
State and analyze the running time of your algorithm.
Faster (in asymptotic Big O notation) and correct solutions are worth more credit.
You will upload a pdf of your typed solution. Handwritten solutions will be penalized. Please see the related threads in Ed Discussions for detailed expectations regarding your submission.