COMP3600/6466 Algorithms Assignment 1
COMP3600/6466 — Algorithms
Convenor & lecturer: Hanna Kurniawati
E-mail: comp 3600 [email protected]
Assignment 1
Due: Friday, 17 August 2019 23:59 Canberra Time
Grace Period Ends: Saturday, 18 August 2019 13:00 Canberra Time
Late Penalty: 100%
Notes:
• 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.
– We strongly suggest you submit your assignment as a draft before the due date. If you submit as a draft,
you can still update your assignment and by the time the grace period ends, the last submitted draft will
automatically become your official submission.
• Assignment marking:
– The total mark you can get in this assignment is 100 points.
– This assignment will contribute 15% to your overall mark.
– We strongly suggest that you do this assignment. The results of this assignment will help you understand
how much you have understood the materials. If you get < 55 in this assignment, it is an indication that
you will likely have trouble in this class and should consider dropping the class before the census date on
31 August 2020.
• Discussion with your colleagues are allowed and encouraged. However, you still need to work on the assign-
ment on your own AND write the names you discussed this assignment with.
Errata and Clarifications (4 August 2020):
• Typo in line-5 of Algorithm 1: A[m] is supposed to be A[mIdx].
• Add a note on the need for explanation in Question 8.
[25 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. (x + y)2 = O(x2 + y2)
2. f (n) = O( f (n)2) when f (n) = Ω(1)
3. log(n!) = O(n log n)
4. f (n) + g(n) = Θ(max( f (n), g(n))
5.
√
n = O(log n)
[35 pts] Part B
6. [20 pts] Please rank the following function by increasing order of growth and explain your answer
1
COMP3600/6466 Algorithms Assignment 1
• f1(n) = n
√
n
• f3(n) = 2n
• f5(n) =
√
2
√
n
• f7(n) = n10020.5n
• f2(n) = ∑ni=0 i3
• f4(n) =
(
n
5
)
• f6(n) = (log n)5
• f8(n) = n(5 log n)2
7. [15 pts]
(a) [10 pts] Please derive the worst case total time required by the algorithm below, assuming they are exe-
cuted in a RAM computational model. Please represent your total time in terms of the size of the input
array (i.e., A.length). This total time is similar to the notation T (n) in https://cs.anu.edu.au/
courses/comp3600/week1-introduction-aftClass.pdf.
Algorithm 1 Sort(An array of integers A)
1: Let n = A.length
2: for i = 1 to n − 1 do
3: Let mIdx = i
4: for j = i + 1 to n do
5: if A[ j] < A[mIdx] then
6: mIdx = j
7: if mIdx , i then
8: tmp = A[i]
9: A[i] = A[mIdx]
10: A[mIdx] = tmp
(b) [5 pts] Please provide the tightest asymptotic bound on the time complexity of the above algorithm.
[40 pts] Part C
8. [20 pts] The town Arrebnac has just been hit by the first case of a new virus, called NV. Let’s call this first
infected person patient-0. Based on the latest census data on Arrebnac’s population and a recent study about
how NV spread, it is identified that under normal circumstances of life at Arrebnac, each infected person will
spread the virus to two other people in Arrebnac everyday.
Medicine to cure people with NV exists. However, once a person is infected, he/she will remain contagious for a
month and infect other people who have not been infected by NV during that time. Furthermore, Arrebnac only
has enough medicine to cure 10,000 infected people, even though it has a population of 400,000. Without the
medicine, the infected person will not survive more than a day after being identified as infected. The healthcare
system of Arrebnac ensures that anyone who is infected can get the medicine if the medicine is available.
Furthermore, the town’s mayor has ordered sufficient NV medicines for the entire population of Arrebnac, right
after patient-0 is infected. However, it will take 10 days before they arrive at Arrebnac.
Assuming there will be no people who can enter nor leave the town, and the only way a person in Arrebnac gets
infected is by direct contact with other infected people who can be linked back to patient-0, will there be any
casualties due to NV if:
(a) [10 pts] Each infected person can be identified and isolated within a day after he/she is infected, such that
the person only infects two other people.
(b) [10 pts] No isolation measure is imposed, which means a person who has infected two people today will
infect yet another two people tomorrow, the day after tomorrow, etc..
Note: In each question above, you need to provide a convincing argument (including mathematical derivation)
that supports your answer.
2
COMP3600/6466 Algorithms Assignment 1
9. [20 pts] The Arrebnac Soccer Dart Association (ASDA) is recruiting new team members. Soccer Dart (https:
//bit.ly/315hKzE) is a combination of soccer and dart, where a player kicks a plastic soccer ball from as
farthest distance as possible while still hitting the bullseye. To ease checking if the ball hits the bullseye or not,
when the ball hits the bullseye, it hits a few hidden nails and the ball becomes flat and can no longer be used for
the day, as it is being repaired.
To recruit good players, ASDA would like to assess the farthest distance an applicant can still hit the bullseye.
To simplify the problem, ASDA assumes each applicant’s performance is always consistent, in the sense that
if during test, an applicant can hit the bullseye from 10m distance, then he/she will always be able to hit the
bullseye from any distance lower than or equal to 10m. ASDA also uses the rule that distance to the dart board
is always rounded down to the closest meter.
Figure 1: An illustration of ASDA’s testing field.
To assess the applicants, ASDA marks the testing field by lines
to indicate the distance of [5m, 6m, 7m, · · · , 55m] from the dart
board (illustrated in Figure 1). Each applicant is then asked to
kick the ball from each line, starting from the nearest distance
(i.e., the 5m line) and sequentially increasing the distance by 1m
until the first line the applicant fails to hit the bullseye. ASDA
officials realise that this strategy is far from efficient, both in the numbers of plastic balls required to assess each
applicant and in the time (due to the number of tries) to assess each applicant.
To help ASDA, please develop a strategy to identify the farthest distance an applicant can still hit the bullseye
if each applicant is limited to:
(a) [10 pts] O(log n) number of tries and unlimited number of plastic balls. Please provide an explanation that
your strategy indeed takes O(log n) number of tries.
(b) [10 pts] Θ(
√
n) number of tries and two plastic balls. Please provide an explanation that your strategy
indeed takes Θ(
√
n) number of tries and at most two plastic balls.
Note: The notation n is the number of kicking positions in the ASDA testing field, i.e., n = 51 in the above
scenario.
3