Hello, I'd like help solving this exercise with explanations please.
A Registered Nurse First Assistant, or RNFA, is a perioperative registered nurse that func- tions as a first assistant during surgical operations. A small clinic has a single operating room. All the RNFA, or nurses, are expected to be able to assist with any surgery planned at the clinic. There are k nurses that will be scheduled to cover n surgeries. The n surgeries, that all take different amounts of time, will be performed in the given order. The duration of each one of the surgeries is given by D = [d, d2, ..., dn). A nurse can be scheduled for zero or more surgeries, but they have to be consecutive. The scheduling will partition the n surgeries into k blocks. The optimal partition will be the one for which the maximum time scheduled for any nurse tmaz is as small as possible. Our goal is to compute tmaz for the optimal partition. Consider the following example: Input The duration of each surgery in minutes, D 40, 75, 25, 20, 90, 45, 30, 35 The number of nurses, k 3 (Aisha, Brooke and Cameron) Optimal schedule nurse Brooke Aisha 1, 2 115 min Cameron 6, 7, 8 surgeries time scheduled 3, 4, 5 135 min 110 min Output The maximum time scheduled for any nurse, tmaz 135 min (for Brooke) The problem can be solved by a clever algorithm in O(n?) time (more about this in a few weeks), but we are going to explore the potential of a divide-and-conquer algorithm, hoping to do even better. The idea is to perform a binary search over some search space, yet to be defined. 1. (5 points) The Inverse Problem Let us first consider the inverse problem: Given a maximum total time t per nurse and the durations of the surgeries D, how many nurses are needed to cover the n surgeries? For the example given in the introduction, here is a list of some values of t and the corre- sponding output k: t (minutes) 90 105 120 135 150 k (nurses) 6 6 4 3 3 Design an algorithm that solves the problem with a running time that is linear in n, the size of the input. Describe your algorithm using pseudocode. Hint A very simple greedy algorithm will solve the problem. 2. Divide and Conquer We have seen how binary search can be used to find an element in a sorted list. We are now going to use the same strategy to find the optimal value tmaz from a range of possible values t. The optimal value in our case is the lowest value t such that the n surgeries can be covered by the k nurses. (a) (2 points) Give a lower bound for the search range, as a function of the input D. Justify your answer. (b) (2 points) Give an upper bound for the search range, as a function of the input D. Justify your answer. (c) (6 points) Use your algorithm from the previous question to implement a binary search over the search range you defined. Describe your algorithm using pseu- docode. 3. Analysis of the Algorithm (a) (2 points) Formulate a recurrence relation that describes the running time T(n, N), where n is the number of surgeries and N is the size of the search range. Hint The divide-and-conquer strategy applies to the search range, the parame- ter N. The number of surgeries n will be the same throughout the itera- tions. (b) (3 points) Solve the recurrence relation in order to obtain the asymptotic running time of the algorithm. Give the expression for N as a function of the input D. A Registered Nurse First Assistant, or RNFA, is a perioperative registered nurse that func- tions as a first assistant during surgical operations. A small clinic has a single operating room. All the RNFA, or nurses, are expected to be able to assist with any surgery planned at the clinic. There are k nurses that will be scheduled to cover n surgeries. The n surgeries, that all take different amounts of time, will be performed in the given order. The duration of each one of the surgeries is given by D = [d, d2, ..., dn). A nurse can be scheduled for zero or more surgeries, but they have to be consecutive. The scheduling will partition the n surgeries into k blocks. The optimal partition will be the one for which the maximum time scheduled for any nurse tmaz is as small as possible. Our goal is to compute tmaz for the optimal partition. Consider the following example: Input The duration of each surgery in minutes, D 40, 75, 25, 20, 90, 45, 30, 35 The number of nurses, k 3 (Aisha, Brooke and Cameron) Optimal schedule nurse Brooke Aisha 1, 2 115 min Cameron 6, 7, 8 surgeries time scheduled 3, 4, 5 135 min 110 min Output The maximum time scheduled for any nurse, tmaz 135 min (for Brooke) The problem can be solved by a clever algorithm in O(n?) time (more about this in a few weeks), but we are going to explore the potential of a divide-and-conquer algorithm, hoping to do even better. The idea is to perform a binary search over some search space, yet to be defined. 1. (5 points) The Inverse Problem Let us first consider the inverse problem: Given a maximum total time t per nurse and the durations of the surgeries D, how many nurses are needed to cover the n surgeries? For the example given in the introduction, here is a list of some values of t and the corre- sponding output k: t (minutes) 90 105 120 135 150 k (nurses) 6 6 4 3 3 Design an algorithm that solves the problem with a running time that is linear in n, the size of the input. Describe your algorithm using pseudocode. Hint A very simple greedy algorithm will solve the problem. 2. Divide and Conquer We have seen how binary search can be used to find an element in a sorted list. We are now going to use the same strategy to find the optimal value tmaz from a range of possible values t. The optimal value in our case is the lowest value t such that the n surgeries can be covered by the k nurses. (a) (2 points) Give a lower bound for the search range, as a function of the input D. Justify your answer. (b) (2 points) Give an upper bound for the search range, as a function of the input D. Justify your answer. (c) (6 points) Use your algorithm from the previous question to implement a binary search over the search range you defined. Describe your algorithm using pseu- docode. 3. Analysis of the Algorithm (a) (2 points) Formulate a recurrence relation that describes the running time T(n, N), where n is the number of surgeries and N is the size of the search range. Hint The divide-and-conquer strategy applies to the search range, the parame- ter N. The number of surgeries n will be the same throughout the itera- tions. (b) (3 points) Solve the recurrence relation in order to obtain the asymptotic running time of the algorithm. Give the expression for N as a function of the input D
