Algorithms and Analysis
COSC 2123/1285
Assignment 2: Algorithm Design & Complexity Analysis
Assessment Type Individual Assignment. Submit online via Canvas → Assign-
ments → Assignment 2. Clarifications/updates/FAQs can be
found in Ed Forum → Assignment 2: General Discussions.
Due Dates Deadline 1 Week 11, October 4, 23:59, for Problems 1-3,
Deadline 2 Week 12, October 16, 23:59, for Problems 4-5
Marks 40
IMPORTANT NOTES
• If you are asked to design an algorithm, you need to describe it in plain En-
glish first, say a paragraph, and then provide an unambiguous pseudo code,
unless specified otherwise. The description must include enough details to under-
stand how the algorithm runs and what the complexity is roughly. All algorithm
descriptions and pseudo codes required in this assignment are at most half a page
in length. Worst-case complexity is assumed unless specified otherwise.
• Standard a
ay operations such as sorting, linear search, binary search, sum,
max/min elements, as well as algorithms discussed in the pre-recorded lectures
can be used straight away (but make sure to include the input and output if you
are using them as a li
ary). However, if some modification is needed, you have to
provide a full description. If you are not clear whether certain algorithms/opera-
tions are standard or not, post it to Ed Discussion Forum or drop Hoang a Team
message.
• Marks are given based on co
ectness, conciseness (with page limits), and clar-
ity of your answers. If the marker thinks that the answer is completely not under-
standable, a zero mark might be given. If co
ect, ambiguous solutions may still
eceive a deduction of 0.5 mark for the lack of clarity.
• Page limits apply to ALL problems in this assignment. Over-length answers may
attract mark deduction (0.5 per question). We do this to (1) make sure you develop
a concise solution and (2) to keep the reading/marking time under control. Please
do NOT include the problem statements in your submission because this
may increase Turnitin’s similarity scores significantly.
• This is an individual assignment. While you are encouraged to seek clarifications
for questions on Ed Forum, please do NOT discuss solutions or post hints leading
to solutions.
• In the submission (your PDF file), you will be required to certify that the submitted
solution represents your own work only by agreeing to the following statement:
I certify that this is all my own original work. If I took any parts from
elsewhere, then they were non-essential parts of the assignment, and they
are clearly attributed in my submission. I will show that I agree to this
honour code by typing “Yes":
2
1 Part I: Fundamental
Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists
of an a
ay A of n integers, two nonnegative integers `,u satisfying 0≤ `≤ u ≤ n−1, and
an integer k. We assume that n is a power of 2.
Algorithm mystery(A[0, . . . , (n−1)],`,u,k)
if `== u then
if A[`]== k then
eturn 1;
else
eturn 0;
end if
else
m = b(`+u−1)/2c;
eturn mystery(A,`,m,k)+mystery(A,m+1,u,k);
end if
a) [2 marks] What does mystery(A[0..(n−1)],0,n−1,k) compute (0.5 mark)? Justify
your answer (1.5 marks).
) [1 mark] What is the algorithmic paradigm that the algorithm belongs to?
c) [2 marks] Write the recu
ence relation for C(n), the number of additions required
y mystery(A,0,n−1,k).
d) [2 marks] Solve the above recu
ence relation by the backward substitution method
to obtain an explicit formula for C(n) in n.
e) [1 mark] Write the complexity class that C(n) belongs to using the Big-Θ notation.
3
Problem 2 (8 marks, 1.5 pages). Let A be an a
ay of n integers.
a) [2 marks] Describe a
ute-force algorithm that finds the minimum difference be-
tween two distinct elements of the a
ay, where the difference between a and
is defined to be |a− b| [1 mark]. Analyse the time complexity (worst-case) of the
algorithm using the big-O notation [1 mark]. Pseudocode/example demonstration
are NOT required. Example: A = [3,−6,1,−3,20,6,−9,−15], output is 2 = 3-1.
) [2 marks] Design a transform-and-conquer algorithm that finds the minimum dif-
ference between two distinct elements of the a
ay with worst-case time complexity
O(n log(n)): description [1 mark], complexity analysis [1 mark]. Pseudocode/ex-
ample demonstration are NOT required. If your algorithm only has average-case
complexity O(n log(n)) then a 0.5 mark deduction applies.
c) [4 marks] Given that A is already sorted in a non-decreasing order, design an al-
gorithm with worst-case time complexity O(n) that outputs the absolute values
of the elements of A in an increasing order with no duplications: description and
pseudocode [2 marks], complexity analysis [1 mark], example demonstration on
the provided A [1 mark]. If your algorithm only has average-case complexity O(n)
then 2 marks will be deducted. Example: for A = [3,−6,1,−3,20,6,−9,−15], the
output is B = [1,3,6,9,15,20].
4
Problem 3. [10 marks, 1.5 pages] (Dijkstra’s algorithm + min-heap) Given a graph
as in Fig. 1, we are interested in finding the shortest paths from the source a to all
other vertices using the Dijkstra’s algorithm and a min-heap as a priority queue. Note
that a min-heap is the same as a max-heap, except that the key stored at a parent node
is required to be smaller than or equal to the keys stored at its two child nodes. In the
context of the Dijkstra’s algorithm, a node in the min-heap tree has the format v(pv,dv),
where dv is the length of the cu
ent shortest path from the source to v and pv is the
second to last node along that part (right before v). For example, b(a,4) is one such node.
We treat dv as the key of Node v in the heap, where v ∈ {a,b, c,d, e, f , g,h}.
a
c
d
e
f
g
h
7
1
5
6
2
15
3
49
7
3
9
1
3
Source
10
Figure 1: An input graph for the Dijkstra’s algorithm. Edge weights are given as integers
next to the edges. For example, the weight of the edge (a,b) is 7.
a) [1 mark] The min-heap after a(a,0) is removed is given in Fig. 2. The next node to
e removed from the heap is c(a,1). Draw the heap after c(a,1) has been removed
and the tree has been heapified, assuming that ∞≥∞ (note: no need to swap if
oth parent and children are ∞). No intermediate steps are required.
c(a, 1)
(a, 7) h(−,∞)
e(−,∞) f(−,∞) g(−,∞)d(a, 5)
Figure 2: The min-heap (priority queue) after a(a,0) has been removed.
) [2 marks] Draw the heap(s) after each neighbour of c has been updated and the
tree has been heapified (see the pseudocode in the lecture Slide 30, Week 9). If there
are multiple updates then draw multiple heaps, each of which is obtained after one
update. Note that neighbours are updated in the alphabetical order, e.g., d must
e updated before e. No intermediate steps, i.e., swaps, are required. Follow the
discussion on Ed Forum for how to update a node in a heap.
5
S: vertices whose shortest
paths have been known
Priority queue of remaining vertices
1 a(a,0) b(a,7), c(a,1),d(a,5), e(−,∞), f (−,∞), g(−,∞),h(−,∞)
2 a(a,0), c(a,1)
3
4
5
6
7
8
Table 1: Complete this table for Part c).
c) [5 marks] Complete Table 1 with co
ect answers. You are required to follow strictly
the steps in the Dijkstra’s algorithm taught in the lecture of Week 9.
d) [2 marks] Fill Table 2 with the shortest paths AND the co
esponding distances
from a to ALL other vertices in the format a →?→?→ v | dv, for instance, a → c | 1.
Shortest Paths Distances
a a → a 0
c a → c 1
d
e
f
g
h
Table 2: Complete this table for Part d).
6
2 Submission
The final submission (via Canvas) will consist of:
• Your solutions to all questions in a PDF file of font size 12pt and your agreement
to the honour code (see the first page). You may also submit the code in Problem 5.
Late Submission Penalty: Late submissions will incur a 10% penalty on the total
marks of the co
esponding assessment task per day or part of day late, i.e, 4 marks pe
day. Submissions that are late by 5 days or more are not accepted and will be awarded
zero, unless Special Consideration has been granted. Granted Special Considerations
with new due date set after the results have been released (typically 2 weeks after the
deadline) will automatically result in an equivalent assessment in the form of a
practical test, assessing the same knowledge and skills of the assignment (location and
time to be a
anged by the coordinator). Please ensure your submission is co
ect and
up-to-date, re-submissions after the due date and time will be considered as late sub-
missions. The core teaching servers and Canvas can be slow, so please do double check
ensure you have your assignments done and submitted a little before the submission
deadline to avoid submitting late.
Assessment declaration: By submitting this assessment, you agree to the assess-
ment declaration - https:
www.rmit.edu.au/students/student-essentials/ assessment-and-
exams/assessment/assessment-declaration
3 Plagiarism Policy
University Policy on Academic Honesty and Plagiarism: You are reminded that all sub-
mitted work in this subject is to be the work of you alone. It should not be shared with
other students. Multiple automated similarity checking software will be used to compare
submissions. It is University policy that cheating by students in any form is not permit-
ted, and that work submitted for assessment purposes must be the independent work of
the student(s) concerned. Plagiarism of any form will result in zero marks being given
for this assessment, and can result in disciplinary action.
For more details, please see the policy at
https:
www.rmit.edu.au/students/student-essentials/assessment-and-results
academic-integrity.
4 Getting Help
There are multiple venues to get help. We will hold separate Q&A sessions exclusively
for Assignment 2. We encourage you to check and participate in the Ed Discussion Fo-
um, on which we have a pinned discussion thread for this assignment. Although we
encourage participation in the forums, please refrain from posting solutions or sugges-
tions leading to solutions.
7
https:
www.rmit.edu.au/students/student-essentials/assessment-and-results/academic-integrity
https:
www.rmit.edu.au/students/student-essentials/assessment-and-results/academic-integrity
Part I: Fundamental
Submission
Plagiarism Policy
Getting Help