CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
• The points that you obtain will depend on the running time of your algorithm. For example, a student who gives a linear-time algorithm will receive more points than a student who gives an algorithm with quadratic running time for a given problem. We have had this discussion on efficiency in class and this is mentioned here again only for emphasis.
There are 7 questions for a total of 40 points.
1. (1 point) Consider the following recursive function:
Let R(n) denote the number of times this function prints “Hello World” given the positive integer n as input. Which of the following are true (you do not need to write the reasons):
A. R(n) = O(n)
B. R(n) = Ω(log2 n) C. R(n)=⌈log3n⌉+1 D. R(n)=⌊log3n⌋+1
F(n)
– If (n > 1) F(⌊n/3⌋)
– Print(“Hello World”)
1 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
2. (4 points) There is an array A[1…n] containing n integers in non-decreasing order. Someone changes the last k elements of this array by replacing array element A[j] with (1000 − A[j]) for all n − k < j ≤ n. You have to design an algorithm Re-Sort(A, n, k) that takes such a modified array A, n, and k as input and outputs a sorted array. Give pseudocode and discuss the running time.
(An example of a valid input for your algorithm is A = [1,6,15,30,3,2] and k = 2 (this means that the initial array must have been [1, 6, 15, 30, 997, 998]). Given (A, n, k) as input, the output should be an array [1, 2, 3, 6, 15, 30].)
2 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
3. (7 points) Town authorities of Algotown are planning for an impending virus outbreak. They want to plan for panic buying and taking cues from some other towns, they know that one of the items that the town may run out of is toilet paper. They have asked your help to figure out whether the toilet paper demand of all n residents can be met. They provide you with the following information:
• There are n residents r1, ..., rn, m stores s1, ..., sm, and p toilet paper suppliers x1, ..., xp.
• The demand of each of the residents in terms of the number of rolls required.
• The list of stores that each of the residents can visit and purchase rolls from. A store cannot put any restriction on the number of rolls a customer can purchase given that those many rolls are available at the store.
• The number of rolls that supplier xj can supply to store si for all i ∈ {1, ..., m} and j ∈ {1, ..., p}. The above information is provided in the following data structures:
• A 1-dimensional integer array D[1...n] of size n, where D[i] is the demand of resident ri.
• A 2-dimensional 0/1 array V [1...n, 1...m] of size n × m, where V [i, j] = 1 if resident ri can visit
store sj and V [i, j] = 0 otherwise.
• A 2-dimensional integer array W [1...m, 1...p] of size m × p, where W [i, j] is the number of rolls of
toilet paper that the supplier xj can supply to store si.
Design an algorithm to determine if the demand of all residents can be met. That is, given (n, m, p, D, V, W ) as input, your algorithm should output “yes” if it is possible for all residents to obtain the required num- ber of rolls and “no” otherwise. Give pseudocode and discuss running time.
(For example, consider that the town has two residents, one store and two suppliers. If D = [2, 2], V = [1 ], and W = [2,2], then the demand can be met. However, if D = [2,2],V = [1 ], and W = [2,1], then the demand cannot be met.)
3 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
4 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
4. (6 points) Given an integer array A[1...n] such that A[1] ≤ A[2] ≤ A[3] ≤ ... ≤ A[n], you want to find an index j such that ni=1|A[i] − A[j]| is minimised. Here |x − y| denotes the absolute value of the difference of numbers x and y. Design an algorithm for this problem. Give pseudocode and argue why your algorithm outputs an index j that minimises ni=1|A[i] − A[j]|.
5 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
6 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
5. Algotown has n residents labelled 1, ..., n. All n residents live along a single road. The Town authorities suspect a virus outbreak and want to set up k testing centers along this road. They want to set up these k testing centers in locations that minimises the sum total of distance that all the residents need to travel to get to their nearest testing center. You have been asked to design an algorithm for finding the optimal locations of the k testing centers.
Since all residents live along a single road, the location of a resident can be identified by the distance along the road from a single reference point (which can be thought of as the starting point of the town). As input, you are given integer n, integer k, and the location of the residents in an integer array A[1...n] where A[i] denotes the location of resident i. Moreover, A[1] ≤ A[2] ≤ A[3] ≤ ... ≤ A[n]. Your algorithm should output an integer array C[1...k] of locations such that the following quantity gets minimised:
n
D(i), where D(i) = min |A[i] − C[j]|
j∈{1,...,k}
Here |x − y| denotes the absolute value of the difference of numbers x and y. Note that D(i) denotes
the distance resident i has to travel to get to the nearest testing center out of centers at C[1],...,C[k]. (For example, consider k = 2 and A = [1,2,3,7,8,9]. A solution for this case is C = [2,8]. Note that for
testing centers at locations 2 and 8, the total distance travelled by residents will be (1+0+1+1+0+1) = 4.)
We will design a Dynamic Programming algorithm for this problem. Let L(i,j) denote the minimum value of total distance travelled by the first i residents (i.e., residents 1, ..., i) if j testing centers were to be opened just for them. (For example, if A = [1, 2, 3, 7, 8, 9], then L(4, 1) = 7.)
Answer the parts that follow:
(a) (1 point) What is the value of L(i, 1) for any positive integer i? You may express your answer in terms of A[1], A[2], ..., A[i].
(Hint: Use ideas developed in problem 4.)
(b) (3 points) Give a recursive formulation for L(i, j) for positive i and j > 1. Give a brief justification for your formulation.
(Hint: Try writing L(i, j) in terms of L(i′, j − 1) for i′ = 1, 2, …, i − 1. Again, you can use ideas from problem 4.)
i=1
7 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
(c) (3 points) Use the recursive formulation developed in part (b) to design an algorithm that outputs the minimum value of the total distance that all residents have to travel if k centers are opened. In other words, your algorithm should output L(n, k).
8 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
(d) (3 points) Make appropriate additions to your algorithm in part (c) so that it outputs an optimal location array C[1…k].
9 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
6. (5 points) Algotown has n residents labeled 1, …, n. The town authorities find that a set S of k residents of the town have been tested positive for a new virus. They want to closely monitor all residents who may be at risk of having the virus. They come up with the following way to define the set of residents who may be at risk of having the virus. A resident i is said to be resident-at-risk if and only if at least one of the following two conditions holds:
(i) i ∈ S (that is, i is one of the residents who have tested positive)
(ii) There is a sequence of residents i, j1 , j2 , …, jt for t > 0 such that every adjacent pair of residents in
this sequence has been in close proximity in the past two weeks and jt ∈ S.
To create a list of all residents who are resident-at-risk, they have conducted a survey where resident i correctly returned a list C[i] of all other residents with whom resident i was in close proximity in the past two weeks. You have been asked to compile a list of all residents who are resident-at-risk given n, S, and C[1],…,C[n] as input. Design an algorithm for this problem. Give pseudocode and discuss running time.
10 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
7. (7 points) Algotown has n residents labelled 1, …, n. In the midst of a virus outbreak, the town author-
ities of Algotown realise that hand sanitiser has become an essential commodity. They know that every
resident in this town requires at least T integer units of hand sanitiser. However, at least ⌈ n ⌉ residents 2
do not have enough sanitiser. On the other hand, there may be residents who may have at least T units. With very few new supplies coming in for the next few weeks they want to implement some kind of sharing strategy. At the same time, they do not want too many people to get in close proximity to implement sharing. So, they come up with the following idea:
Try to pair up residents (based on the amount of sanitiser they possess) such that: 1. A resident is either unpaired or paired with exactly one other resident.
2. Residents in a pair together should possess at least 2T units of sanitiser. 3. The number of pairs is maximised.
Once such a pairing is obtained, the residents who are left out (that is, unpaired residents) can be managed separately. The town authorities have conducted a survey and they know the amount of sanitiser every resident possesses. You are asked to design an algorithm for this problem. You are given as input integer n, integer T , and integer array P [1…n] where P [i] is the number of units of sanitiser that resident i possesses. You may assume that 0 ≤ P [1] ≤ P [2] ≤ … ≤ P [n]. Your algorithm should output a pairing as a list of tuples (i1, j1), (i2, j2), …, (ik, jk) of maximum size such that (i) For all t = 1, …, k, P[it]+P[jt]≥2T and(ii)i1,…,ik,j1,…,jk aredistinct. Givepseudocodeanddiscussrunningtime.
11 of 12
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2020) Take-home Final
12 of 12