This assignment is for both COMP3027 and COMP3927 students.

Task 1: Social Distancing [30 marks]

You and your genius friend earned enough licensing fees from the deep quantum neural networks to retire. Finally, you can indulge in your lifelong dream of running a fleet of Mexican food buses called Nacho Bus-iness. You want to set them up along a street in downtown for Cinco de Mayo. However, due to social distancing requirements, the buses cannot be placed too close together. Your goal is to find a placement of the buses satisfying the social distancing requirement that maximizes total revenue.

Formally, you are given as input an array R of n positive integers (not necessarily distinct) and the social distancing requirement d ≥ 0. The integer R[i] is the amount of revenue earned by a food bus placed at location i on the street. You can place as many buses as you wish, subject to the social distancing requirement: if a bus is placed at location i, then the nearest location that we can place another bus is i−d and i+d; no other bus can be placed at locations i−d+1,…,i+d−1. Your goal is to design an efficient dynamic programming algorithm to determine the maximum revenue that can be earned by a placement of food buses that satisfy the social distancing requirement. (Note that we are only interested in the revenue, not the actual placement.)

For example, consider the input R = [3027, 3927, 2123, 2823, 3530, 5045] and d = 3. The optimal solution is to place buses at locations 1 and 5 for a total revenue of 3927 + 5045 = 8972. For the same R and d = 2, the optimal solution is to place buses at locations 1, 3 and 5 for a total revenue of 3927 + 2823 + 5045 = 11795. (Arrays start with index 0.)

3027
Figure 1: Optimal solution for d = 2

3027
Figure 2: Optimal solution for d = 3

What we expect to see: Definition of OPT(…), and its parameters

What we expect to see: a recurrence that relates each subproblem to “smaller” subproblems. We just want to see a clear description of the recurrence here. The justification for the recurrence goes into (e).

What we expect to see: A description of the base cases and the values that OPT(..) takes on these base cases.

using the optimal values of the subproblems.

What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a base case, the correctness of the recurrence and the values for the base cases, and that you correctly obtained the optimal revenue from OPT(..).

(f) Prove the time and space complexity of your algorithm.

What we expect to see: An analysis of the running time and space required to compute all the OPT(..) values and to obtain the maximum revenue from OPT(..)

Task 2: Grid Climbing [70 marks]

Congratulations! You’ve made it to the finals of the World Grid Climbing competition. You start at the bottom-left corner of an n × m grid and are only allowed to climb rightwards or upwards. Each grid position (i, j) has a score S[i, j]. (The bottom-left position is (0, 0) and the top-right is (n − 1, m − 1).) You have an energy budget of B. Moving right costs cr amount of energy and moving up costs cu. The numbers B, cr and cu are non-negative integers. A climbing path consists of a sequence of rightwards and upwards moves and is feasible if the total energy cost is at most the budget. The goal is to find the maximum total score that can be obtained by a feasible climbing path. (Note that we are only interested in the score, not the actual path.)

For instance, suppose S is the following grid, B = 10, cu = 3, and cr = 1. Then, the optimal path is (0,0) → (0,1) ↑ (1,1) → (1,2) → (1,3) ↑ (2,3) for a total score of 5+4+100+7+9+10 = 135 and cost of 2 × cu + 4 × cr = 10.

2145 8 3 9 10 3 100 7 3 5468

Figure 3: The grid S

2145 8 3 9 10 3 100 7 3 5468

Figure 4: The optimal path

For COMP3027: your algorithm should take O(nmB) time and space for full marks. For COMP3927: your algorithm should take O(nm) time and space for full marks; an O(nmB) time and space algorithm is worth 50 marks.

What we expect to see: Definition of OPT(…), and its parameters

What we expect to see: a recurrence that relates each subproblem to “smaller” subproblems. We just want to see a clear description of the recurrence here. The justification for the recurrence goes into (e).

What we expect to see: A description of the base cases and the values that OPT(..) takes on these base cases.

using the optimal values of the subproblems.

What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a base case, the correctness of the recurrence and the values for the base cases, and that you correctly obtained the optimal score from OPT(..).

What we expect to see: An analysis of the running time and space required to compute all the OPT(..) values and to obtain the optimal score from OPT(..).

Submission details

Exemplar for Knapsack