Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP3600/6466 Algorithms Assignment 1
COMP3600/6466 — Algorithms
Assignment 1
Due: Friday, 20 August 2020 23:59 Canberra Time
Grace Period Ends: Saturday, 21 August 2020 13:00 Canberra Time
Late Penalty: 100%
IMPORTANT NOTES (PLEASE READ BEFORE WORKING ON THE SOLUTION):
? Please submit your assignment as a single .pdf file, named A1-[studentID].pdf, via Wattle before the due date.
? We provide 13 hours grace period. This means, there will be no penalty if you submit before the grace period
ends. However, we will NOT accept assignment submission beyond this time (i.e., late penalty after the grace
period ends is 100%).
– You can update your assignment until the grace period ends.
? Assignment marking:
– The total mark you can get in this assignment is 90 points.
– This assignment will contribute 20% to your overall mark.
– In each question, you need to provide a convincing argument (including mathematical derivation) that
supports your answer. The argument is worth 80% of the marks, while the solution alone is 20%.
? Discussion with your colleagues are allowed and encouraged. However, you need to work on the assignment
on your own AND write the names you discussed this assignment with.
In all the questions below, you can assume that all n are positive integers, while all f (n) and g(n) are asymptotically
positive functions —that is, a function whose value is positive for all sufficiently large n.
[15 pts] Part A
For each statement below, please identify if the statement is Always True, Sometimes True, or False and provide your
reasoning. Each question is worth 5 points.
1. f (n) + o( f (n)) = Θ( f (n))
2. f (n) = ?(g(n)) implies g(n) = ?( f (n))
3. f (n) + g(n) = ?(min( f (n), g(n)))
[35 pts] Part B
4. [15 pts] Please rank the following function by increasing order of growth and explain your answer
? f1(n) = dlog(n)e!
? f2(n) = log(n!)
? f3(n) = nlog n
? f4(n) = n2
? f5(n) = 2
√
2 log(n)
5. [20 pts] Ms Tree was given the following algorithm to be implemented and analyse.
Can you please help Ms Tree by answering the following questions:
(a) [5 pts] Given a tree T with n nodes, what does the algorithm AFunction compute?
1
COMP3600/6466 Algorithms Assignment 1
Algorithm 1 AFunction(A binary tree T )
1: if T == ? then
2: Return 0
3: if T .root.le f tChild == ? AND T .root.rightChild == ? then
4: Return 1
5: Return AFunction(T .root.le f tChild) + AFunction(T .root.rightChild)
(b) [7.5 pts] Please provide the total running time T (n) for AFunction in the form of a recurrence function,
when given a tree T with n nodes as input.
(c) [7.5pt] Please solve the above recurrence using substitution method when the tree is a complete binary
tree —that is, a binary tree where all non-leaf nodes have two children and all leaves are at the same level.
Please frame the solution as a tight asymptotic bound (i.e., Θ).
[40 pts] Part C
6. [15 pts] 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. [25 pts] 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
2
COMP3600/6466 Algorithms Assignment 1
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.