Rental reservations

As in Assignment 6, you are thinking about renting out your cabin to visitors over the summer. But you
realized: why would I try to maximize the number of bookings? Since I charge per day, I should be
trying to maximize the amount of time that the cabin is rented! Once again, you are given a collection
of reservations from people who would like to rent the cabin for a specific interval of time, and we want
an algorithm that selects a non-overlapping set of reservations so that the total amount of rental time
is maximized. The problem can be formalized as follows:
CABIN RENTAL PROBLEM
INPUT: A set of rental reservations, represented by a set of intervals R = {I0
, . . . , In−1
}, where Ik =
(sk
, ek
) with sk < ek for k ∈ {0, . . . , n − 1}. For each rental reservation Ik , the value sk represents the start time and ek represents the end time. The start and end of summer are represented by variables t0 and t1 , so that the cabin is available to be rented within the interval T = [t0 , t1 ]. Assume that all reservations in R are for times within T: that is, t0 ≤ sk < ek ≤ t1 . Definition of ‘feasible solution’ for this problem: A subset of reservations S ⊆ R is a feasible solution if no two reservations in S overlap. Formally: ∀Ia , Ib ∈ S, Ia ∩ Ib = ∅. Definition of ‘objective function’ for this problem: For any feasible solution S, the objective function c(S) is the sum of the lengths of the reservations in S. In other words, the objective function measures how ‘good’ a certain solution is (i.e., the total rental time). Formally: c(S) = X Ik∈S |Ik |. I am using the notation |Ik | to mean the length of a reservation: |Ik | = ek −sk . TO OUTPUT: A feasible solution S ⊆ R that maximizes the objective function. Such an S is called maximal. Formally: output a feasible solution S such that, for all other feasible solutions S 0 , we have c(S) ≥ c(S 0 ). 1 Assumptions and Notation: • Assume that the reservations in R are always sorted by end times, i.e., e0 ≤ ··· ≤ en−1 In real life, we could ensure this by sorting the reservations first, in O(n log n) time. • For each j ∈ {0, . . . , n − 1}, we will use the notation Rj to denote the first j + 1 reservations in R, i.e., define Rj = {I0 , . . . , Ij }. For example, R0 = {I0 } and Rn−1 = R. • For any j ∈ {0, . . . , n−1}, the following function F(j) is meant to calculate the maximum possible value of the objective function out of all feasible solutions for the subset of reservations Rj : F(j) =    0 if j < 0 if j = 0 max{F(j − 1), ej − sj + F(m)} if j > 0,
where m is the largest index in {0, . . . , j − 1} such that em < sj , or m = −1 if no such em exists. Most of the challenge in this assignment is getting used to the various definitions, terminology, and notation given above. Questions 1-5 are intended to help you get familiar with them. (2 pts) We described above what 1. F(j) is meant to calculate, but the mathematical definition of F(j) is incomplete. What expression should be substituted for the empty box in the definition of the function F(j)? (2 pts) Let 2. R = {I0 , . . . , In−1 } be a set of reservations, and let S be any maximal solution for input R. Suppose we have access to an algorithm that accurately computes the value of F(j) for us when we give it any value of j ∈ {0, . . . , n − 1}. How could we use such an algorithm to compute c(S)? In other words: what is the relationship between c(S) and the function F(j)? (4 pts) In the given mathematical definition of 3. F(j), the case where j > 0 computes the maximum of two
values. Explain in English what these two values represent in terms of cabin rental reservations
(i.e., instead of technical terms, only use language about cabin rentals that a random person on the
street would understand.)
(2 pts) State the Optimal Substructure Property for the Cabin Rental Problem given on this assignment. 4.
Hint: Use the posted solutions from Assignment 6 for a good starting point! There are important
changes to make, but there shouldn’t be many.
(4 pts) Prove the Optimal Substructure Property that you stated in question 4. 5.
Hint: Use the posted solutions from Assignment 6 for a good starting point! There are important
changes to make, but there shouldn’t be many.
2
For questions 6–11, refer to the following code that returns the maximum possible value of the objective function for the set of reservations stored in the input array R. Assume that each reservation
Ik
is stored in the input array R as R[k][0] = sk and R[k][1] = ek
.
1 public int FCompute (int [][] R) {
2 return FRecurse (R, R.length-1); //R.length is the number of reservations in R
3 }
4
5 private int FRecurse (int [][] R, int j) {
6 if (j < 0) 7 result = 0; 8 else if (j == 0) 9 result = R[j][1] - R[j][0]; 10 else if (j > 0) {
11 int k = j-1;
12 while (k >= 0 && R[k][1] >= R[j][0])
13 k--;
14 result = Math.max( FRecurse(R, j-1) , R[j][1] - R[j][0] + FRecurse(R, k) );
15 }
16 return result;
17 }
(2 pts) Does the code for 6. FCompute and FRecurse use dynamic programming? Explain your answer.
(2 pts) What is the purpose of executing Lines 11, 12, and 13 in 7. FRecurse?
(Write more than “it calculates k". What does k represent and why is it important?)
(3 pts) Consider an execution of 8. FCompute when the input is an array R of n reservations.
Let f (n) be the total number of times that Line 6 of FRecurse is executed in the worst case as a
function of n. Give a recurrence relation that defines f (n).
(4 pts) Give a solution to your recurrence relation for 9. f (n) using asymptotic notation (Big-Oh or Big-Theta
notation). Show the steps you used to come up with your answer, but you do not need to submit a
full proof that it is correct. (For example, you can use the substitution method, but you don’t need
to also include an induction proof.)
(3 pts) Using memoization, modify the code for 10. FCompute and FRecurse to give a significant improvement in the running time (without removing the recursive calls from the code). Write out your new
version of the code and circle (or somehow highlight) what is different from the original.
(2 pts) In terms of the number of reservations 11. n in array R, what is the asymptotic worst-case running time
of your dynamic programming algorithm from question 10? Express your answer using asymptotic
notation (Big-Oh or Big-Theta notation). Justify how you came up with your answer.
(As discussed in lecture, the running-time analysis for top-down dynamic programming is often not
exact. Consult the lectures to see examples of how upper bounds can be determined and justified.)
3
For questions 12–14, refer to the following iterative code that computes values for the table sols.
1 public int [] rentalIterative (int [][] R) {
2 int n = R.length; //n is the number of reservations in R
3 int [] sols = new int [n];
4
5 for (int j = 0 ; j < n ; j++) { 6 if (j == 0) 7 sols[j] = R[j][1] - R[j][0]; 8 else if (j > 0) {
9 int k = j-1;
10 while (k >= 0 && R[k][1] >= R[j][0])
11 k--;
12 if (k >= 0)
13 sols[j] = Math.max( sols[j-1] , R[j][1] - R[j][0] + sols[k] );
14 else
15 sols[j] = Math.max( sols[j-1] , R[j][1] - R[j][0] );
16 }
17 }
18 return sols;
(2 pts) Does the code for 12. rentalIterative use dynamic programming? Explain your answer.
(4 pts) What is the worst-case running time of 13. rentalIterative? Use an analysis similar to what we
did in Week 4 of the course (i.e., counting steps), and then express your answer using asymptotic
notation (Big-Oh or Big-Theta notation).
You do not need to write a proof that your asymptotic notation is correct. You can assume that each
line of code contains O(1) primitive operations (i.e., each line is 1 step).

14. [Additional question (not submitted or graded)]
    Describe how to modify the code for rentalIterative to give an asymptotic improvement on
    the worst-case running time.
15. [Additional question (not submitted or graded)]
    Notice that rentalIterative calculates every value sols[j] in its table sols. Referring back
    to your answer to Question 10 that uses memoization: Can you think of an input set of reservations
    R that would force the algorithm to compute every table entry? Does there exist an input set of
    reservations R for which the algorithm would compute fewer table entries? Which kind of dynamic
    programming do you think is more appropriate for solving this assignment’s version of the Cabin
    Rental Problem?
16. [Additional question (not submitted or graded)]
    "Ugh, dynamic programming is complicated. Didn’t we already solve this problem using a greedy
    algorithm on Assignment 6?" For this assignment’s version of the problem, demonstrate that none
    of the greedy approaches from Assignment 6 will work, i.e., none of them will always produce a
    maximal feasible solution. For each greedy strategy, you just need to produce one example of an
    instance where it doesn’t return a maximal solution.