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 Date Week 12, 11:59pm, May 27, 2022
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 is a binary
tree, or more precisely, its root R. We denote by RLeft and RRight the left and the right
children of R in the tree.
Algorithm mystery(R : root of a binary tree)
if R =∅ then
eturn 0;
else
eturn 1+mystery(RLeft)+mystery(RRight);
end if
a) [2 marks] What does the algorithm compute? Justify your answer.
) [1 mark] What is the algorithmic paradigm that the algorithm belongs to?
c) [2 marks] Assume that the tree is a perfect binary tree of height h (a binary tree
is called perfect if every non-leaf node has precisely two children and all leaf-nodes
are at the same level). Write the recu
ence relation for C(h), the number of addi-
tions required by mystery(). Convention: a single-node tree has height 0.
d) [2 marks] Solve the above recu
ence relation by the backward substitution method
to obtain an explicit formula for C(h) in h for the perfect binary tree of height h.
e) [1 mark] Write the complexity class that C(h) belongs to using the Big-Θ notation.
Problem 2 (8 marks, 1.5 pages). The Australian Government Department of Health
maintains a list of n people who have been double vaccinated against Covid, called
list_double. At the end of 2022, an aggregated list of m people who have been vac-
cinated the third time in 2022 with booster shots is created, called list_triple. Note
that m ≤ n. People in each list are identified by their unique ID numbers (e.g., passport
numbers) and are entered into the lists in chronological order. It is required to design
an algorithm that takes as input the two lists and returns a new list of people who are
double vaccinated but haven’t received their third shots. A reminder will be sent to all
people in this list to take their booster shots.
a) [2 marks] Design (describe + complexity analysis) a
ute-force algorithm that per-
forms the aforementioned task [1 mark]. Analyse the time complexity of the algo-
ithm using the big-O notation [1 mark]. Pseudocode is NOT required.
) [3 marks] Design (describe + complexity analysis) a transform-and-conquer algo-
ithm with time complexity O(n logm) that performs the aforementioned task using
at most a constant amount of extra space (apart from the input/output).
c) [3 marks] Design (describe + pseudocode + complexity analysis) an algorithm with
(average-case) time complexity O(n) that performs the aforementioned task [2 marks].
There is NO restriction on the space complexity.
3
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
4
8
6
3
6
1
4
1
1
4
2
2
73Source
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 4.
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 b(a,4). Draw the heap after b(a,4) has been removed
and the heap has been heapified (fixed), assuming that ∞≥∞. No intermediate
steps are required.
(a, 4)
c(a, 8) d(a, 6)
e(−,∞) f(−,∞) g(−,∞) h(−,∞)
Figure 2: The min-heap (priority queue) after a(a,0) has been removed.
) [2 marks] Draw the heap(s) after the neighbours of b have been updated and the
heap 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.,
must be updated before c. No intermediate steps are required. Follow the dis-
cussion on Ed Forum for how to update a node in a heap.
4
S: vertices whose shortest
paths have been known
Priority queue of remaining vertices
1 a(a,0) b(a,4), c(a,8),d(a,6), e(−,∞), f (−,∞), g(−,∞),h(−,∞)
2 a(a,0),b(a,4)
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 → b | 4.
Shortest Paths Distances
a a → a 0
a → b 4
c
d
e
f
g
h
Table 2: Complete this table for Part d).
5
2 Part II: Advanced
Problem 4 (7 marks, 2 pages). Each Bitcoin transaction, in its simplest form, has one
input coin and several output coins (see Fig. 3). The input coin is genuine in the sense
that it is spent by the transaction. This creates the issue of traceability for Bitcoin, that
is, the entire history of each coin can be traced, e.g., how it was created, split, spent, and
y which users, etc., which can sometimes be too revealing and undesirable for the users.
To make the cryptocu
ency untraceable, it has been proposed that instead of using only
genuine inputs, the cryptocu
ency wallet should also include other fake inputs so that
an observer won’t know which input is the genuine one for that transaction. We will
ignore the fact how this can be done technically and only focus on the mixing part where
genuine and fake inputs are mixed in the transactions to provide untraceability. Assume
that each coin can be used as a genuine input for exactly one transaction and that the
number of coins is the same as the number of transactions in the system.
Figure 3: Example of input and output coins in a Bitcoin transaction.
Figure 4: Examples of mixing genuine and fake inputs for transactions to provide
untraceability. The mixing strategy in a) fails because an observer can determine a
unique mapping M that matches genuine coins with transactions: M[1] = 2, M[2] = 3,
M[3]= 4, and M[4]= 1. The mixing in b) is not the best in disguising the actual mapping,
ut still confuses an observer as there are two possibilities to match the coins with the
transactions.
The mixing strategy sometimes fails because not all mixings are done in a proper way.
For example, in Fig. 4 a), an observer can determine which coin is the genuine input of
which transaction for ALL the coins. We refer to such a mixing as a bad mixing strategy.
6
Note that a mixing strategy can be described by a bipartite graph with the left-side
vertices co
esponding to the coins and the right-side vertices co
esponding to the trans-
actions, and there is an edge between a coin Ci and a transaction T j if Ci is included in
T j as an input (genuine or fake). Design an algorithm of time complexity O(n+m), where
n is the number of coins (or equivalently, the number of transactions) and m is the num-
er of edges in the bipartite graph, that determines if a particular mixing is bad, i.e.,
a unique mapping M that maps ALL coins to their co
esponding transactions could be
found. The algorithm must output M if the mixing is bad.
a) [3 marks] Describe the algorithm