graph algorithms, divide and conquer, greedy algorithms, dynamic programming, network flows, computational intractability.About
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: F(n) - If (n > 1) F(bn/3c) - Print(“Hello World”) 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) = dlog3 ne+ 1 D. R(n) = blog3 nc+ 1 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="[" 11="" ],="" and="" w="[2," 2],="" then="" the="" demand="" can="" be="" met.="" however,="" if="" d="[2," 2],="" v="[" 1="" 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="" ∑n="" i="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="" ∑n="" i="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∑="" i="1" d(i),="" where="" d(i)="min" j∈{1,...,k}="" |a[i]−="" c[j]|="" 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.) 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 dn2 e residents 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