Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 1 [20 marks total]
Consider the following undirected graph, in which each node is labeled using one letter.
a. [10 marks] Draw a depth-first search tree for the above graph, starting from node a, as generated by the DFS algorithm given below.
DFS(G)
1 2 3 4 5 6
foreachu∈G.V u.colour = WHITE
u.parent = NULL
for each u ∈ G.V in alphabetical order
if u.colour == WHITE DFS-VISIT(G, u)
DFS-VISIT(G, v)
1 2 3 4 5 6
v.colour = GREY
for each u ∈ G.Adj[v] in alphabetical order
if u.colour == WHITE u.parent = v
DFS-VISIT(G, u) v.colour = BLACK
Page 1 of 6
Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
b.
[10 marks] Draw a breadth-first search tree for the above graph, starting from node s = a, as generated by the BFS algorithm given below.
BFS(G, s)
1 2 3 4 5 6 7 8 9
10 11 12 13 14
foreachu∈G.V u.colour = WHITE
u.parent = NULL s.colour = GREY
Q.initialise() Q.enqueue(s)
while not Q.isEmpty()
v = Q.dequeue()
for each u ∈ G.Adj[v]
if u.colour == WHITE u.colour = GREY
u.parent = v
Q.enqueue(u) v.colour = BLACK
Page 2 of 6
Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 2 [15 marks total]
Given the following divide and conquer recursive algorithm, find the tight asymptotic bound on the com- plexity function T(n), knowing that the function MERGE takes 3 parameters, each of them is an array of size n/3, and has an asymptotic tight bound of Θ(n). Justify your answers by using the master theorem. Show your working.
MY-DIVIDE-AND-CONQUER(W )
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
/ W is an array of size n, and W (0), W (1),and W (2) are arrays of size n/3 / X is an array of size n, and X(0), X(1),and X(2) are arrays of size n/3 W (0).initialise()
W (1).initialise()
W (2).initialise() n = W. length ifn≤1
return W fori=0 to n−1
if i mod 3 == 0
W (0).append(wi)
else
if i mod 3 == 1
X(0) = X(1) = X(2) =
W (1).append(wi) else
W (2).append(wi) MY-DIVIDE-AND-CONQUER(W (0)) MY-DIVIDE-AND-CONQUER(W (1)) MY-DIVIDE-AND-CONQUER(W (2))
X = return X
MERGE(X(0), X(1), X(2))
Page 3 of 6
Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 3 [15 marks] Given the recurrence
T(n) = T(⌊n/3⌋) + T(⌊2n/3⌋) + cn
a. [5 marks] Make an informed guess of the asymptotic upper bound using any method you prefer. Provide justification for your guess and make sure it is as tight as possible.
b. [10 marks] Solve the provided recurrence using the substitution method to prove the suggested asymptotic upper bound you provided in part a of this question. Clearly describe your inductive assumptions and boundary conditions, and show your working.
Page 4 of 6
Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 4 [25 marks]
This question involves performing an amortised analysis of a data structure.
A Robot is designed to complete optional tasks stored in its memory. New tasks are found regularly and added to the Robot tasks list T. The Robot memory, list T, has a maximum capacity of n tasks. Once a task is completed it is removed from the list T. However, if a new task is found while the Robot memory is full, then this Robot is programmed to remove old tasks to make space for storing newly discovered tasks. The operation NEW-TASK(x) inserts a new task x into list T.
The implementation uses an array T of size n, and an integer task where 0 ≤ task ≤ n. The array T is indexed from zero and the next free slot (if any) is at position task within the array T .
NEW-TASK(x)
1 2 3 4
iftask==n
REMOVE-OLD(T ) / Remove ⌈n/3⌉ oldest tasks from T and make task = n − ⌈n/3⌉
T[task] = x task = task + 1
NEW-TASK(x) is called when the list T is full, (i.e. task == n), then ⌈n/3⌉ oldest tasks will be removed
If
from T, then task x will be inserted into T. The removal is performed by operation REMOVE-OLD which will also update the value of task to be n − ⌈n/3⌉.
a. [10 marks] Starting from an empty list T (i.e. task == 0), assume that the Robot has found m new tasks. How many times will the operation REMOVE-OLD be called? Provide an exact answer (not order of magnitude) in terms of m (the number of operations) and n (the size of T ). Assume that the Robot didn’t complete any operation during the time of founding the m new tasks.
b.
c.
[10 marks] Assuming that the procedure REMOVE-OLD(T) has a worst-case time complexity of Θ(n), use the aggregate method to determine an upper-bound on the worst-case time complexity of any sequence of m consecutive NEW-TASK(x) operations, starting from an empty collection (i.e. task = 0). Answer in terms of m (the number of operations) and n (the size of T ). Make your bound as tight as possible, and show your working.
[5 marks] Based on your answer to part (b) of this question, what is the amortised cost per NEW-TASK operation, over a sequence of m consecutive NEW-TASK operations, starting from an empty collection?
Page 5 of 6
Semester Two Final Examinations, 2020 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 5 [25 marks total]
You have just been appointed as the manager of the first team at Redlands United Football Club. You have been assigned a budget of B (measured in thousands of dollars) to spend on new players to improve the performance of your team. Luckily, you have a smart associate who has already done some scouting and has provided you with some candidate players to help you spend your budget wisely.
Within your team, there are n positions that need to be filled, p1, p2, …, pn.
•Some positions need improvement more than others. The need for a player in position pi is a real
number N[i], where for all i, 0 ≤ N[i] ≤ 1.
•For each of these positions, your associate has scouted two candidate players to sign, player a and
player b. You may only sign one player in each position.
•The cost of player a in position pi is given by Va[i] (measured in thousands of dollars). If you choose
to sign player a to position pi, the value added to your squad is N[i] × Va[i].
•The cost of player b in position pi is given by Vb[i] (measured in thousands of dollars). If you choose
to sign player b to position pi, the value added to your squad is N[i] × Vb[i].
•Since all the n positions need to be filled, it is safe to assume that ni=1 min(Va[i], Vb[i]) ≤ B.
Your goal as manager is to maximise the value added to your squad by signing new players. You must however ensure that you remain within the budget, so the sum of the values of the signings you make must be less than or equal to B.
a. [10 marks] Let Max-Added-Value(i, b) be the maximum added value you can achieve by signing players in positions pi+1,…,pn with a remaining budget of b, where 0 ≤ i ≤ n and 0 ≤ b ≤ B. The solution to the overall problem is Max-Added-Value(0, B).
Give a recurrence defining Max-Added-Value(i, b) for 0 ≤ i ≤ n and 0 ≤ b ≤ B.
b.
You do NOT have to give a dynamic programming solution, just the recurrence.
Be sure to define the base cases of the recurrence as well as the more general cases.
[10 marks] For the dynamic programming solution, indicate in what order the elements of the matrix Max-Added-Value corresponding to the recurrence should be calculated. As part of answering this question, give pseudocode indicating the evaluation order.
c. [5 marks] What is the time complexity of your dynamic programming algorithm? Justify your answer.
END OF EXAMINATION
Page 6 of 6