2023年11月25日

算法代写 | COMP3600/6466 Algorithms Assignment 1

本次代写是算法相关的理论题作业

6.In a galaxy far far away, the Planet Htrae is fighting a health crisis over the spread of a new highly
contagious disease, called DV. The Senate of Planet Htrae is discussing the standard medical procedure to be
adopted to keep its residents safe. For discussion, the health officials of Htrae proposes three different health
measure plans, as described below.

All the proposed health measure plans allow an infected person to be identified and contained (such that the
person can no longer infect another person) within a day. However, during that one day, the infected person
may have spread the disease to others. The rate of spreading and fatality for the different health measure plan
are as follows.

Plan-1. Under this strategy, each infected person can infect at most 12 other people within a day, while the
fatality rate among the infected is 10%.

Plan-2. Under this strategy, each infected person can spread the virus to at most 5 other people within a day.
Under this plan, the fatality rate among the infected remains 10%.

Plan-3. Under this strategy, each infected person can spread the virus to at most 5 other people within a day.
However, the fatality rate among the infected is only 0.1%.

Since Htrae is governed by technocrats and the population of Htrae is huge, the government asked the health
officials to provide asymptotic analysis with respect to fatality rate on the different plans above. To this end,
please help the health officials by answering the following questions.
Suppose the number of people infected at the end of day-0 is 1. Then,

(a) [6 pts] Please define the tight asymptotic bound (i.e., ) on the number of fatalities due to DV under each
plan, as the days progress.

(b) [3 pts] Are there any clear winner on which plan should be applied to minimize the number of fatalities,
based on asymptotic bound and their equivalence classes on the growth in the number of fatalities?

(c) [3 pts] Are there any clear winner on which plan should be applied to minimize the number of fatalities,
based on actual growth in the number of fatalities under the different plans?

(d) [3 pts] Based on the results of (a)-(c), please elaborate when would analysis on asymptotic bound of the
growth of a function be sufficient, and when would such an analysis be insufficient?

7. To welcome new students to the UNA university, each student receives a voucher of $d, which can
be used to purchase stationery and snacks. To reduce queueing time, UNA has packaged n different stationery
packs and n different snack packs, so that students just need to pick exactly one of the stationery packs and
exactly one of the snack packs. You can assume that every student has the full option (i.e., n stationery and n
snack packs). Now, of course, different packs may have different prices. Given this scenario, many students
would like to purchase the pair of stationery and snack packs with the total cost under $d but is as close as
possible to $d. Please help these students by answering the following questions.

(a) [10 pts] Mr SP said that a (n2) algorithm can find the desired pair of stationery and snack packs. Is
he correct? If he is, please provide the algorithm along with the analysis. Otherwise, please provide an
explanation why such an algorithm is not possible.

(b) [15 pts] Mr SP2 said that actually, a O(n log n) algorithm can find the desired pair of stationery and snack
packs. Is he correct? If he is, please provide the algorithm along with the analysis. Otherwise, please
provide an explanation why such an algorithm is not possible.