Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4500/7500 Advanced Algorithms & Data Structures
This exam paper must not be removed from the venue
Examination Duration: 120 minutes
Reading Time: 10 minutes
Exam Conditions:
This is a Central Examination
This is a Closed Book Examination - specified materials permitted
During reading time - write only on the rough paper provided
This examination paper will be released to the Library
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)
Calculators - No calculators permitted
One A4 sheet of handwritten or typed notes double sided is permitted
Materials To Be Supplied To Students:
1 x 14-Page Answer Booklet
Instructions To Students:
Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request.
Answer all questions in the answer book provided. You must hand in your crib
sheet when you submit your examination.
Question 1 [10 marks total]
Solve the following recurrence equations to get a tight asymptotic bound on the complexity of the cor-
responding functions. Justify your answers by using the master theorem. Show your working. You may
assume that T (n) = Θ(1) for suitable constant n. (You may leave logarithmic expressions in your answers
if they evaluate to nonintegral values.)
a. [5 marks] T (n) = 8T (n2 ) + n(n+ 1)
b. [5 marks] T (n) = 3T (n4 ) + n log2 n
Question 2 [10 marks] Given the recurrence
T (n) = 1 for 1 ≤ n < 8
T (n) = T (bn/4c) + T (b3n/4c) + n for n ≥ 8
prove that T (n) ∈ O(n log2 n) using the substitution method. Clearly describe your inductive assumptions
and boundary conditions, and show your working. Justify that what you have proven is sufficient to show
that T (n) ∈ O(n log2 n) by referring to the definition of O-notation.
Question 3 [20 marks]
This question involves performing an amortised analysis of a data structure.
Consider the following implementation of a collection of integers that has an operation INSERT(x) that
inserts integer x into the collection.
The implementation uses an array A of size n, and an integer size where 0 ≤ size ≤ n. The array A is
indexed from zero (i.e. A[0] is the first element of the array). The current elements of the collection are
stored in the first size positions of the array A. For the purpose of this question you may assume that n is
a power of two and that n ≥ 2. Initially, a new collection of integers has no elements (i.e. size == 0).
INSERT(x)
1 if size == n
2 REARRANGE(A) // rearranges the elements of array A
3 size = n/2
4 A[size] = x
5 size = size+ 1
If INSERT(x) is called when size < n then element x is inserted into the collection. Otherwise, if INSERT(x)
is called when the array is already full (i.e. size == n), then n/2 elements of the array are first removed,
and then x is inserted into the collection. The removal is performed by first using operation REARRANGE
to rearrange the elements of A so that the elements to be removed are in the last half of the array A, and
then updating size to be n/2.
a. [10 marks] Exactly how many times will line 2 of INSERT be called in any sequence of m consec-
utive INSERT operations, starting from an empty collection (i.e. one in which size == 0). Answer in
terms of m (the number of operations) and n (the size of A).
b. [8 marks] Given that the procedure REARRANGE on line 2 of INSERT has a worst-case time com-
plexity of Θ(n), use the aggregate method to determine an upper-bound on the worst-case time
complexity of any sequence of m consecutive INSERT operations, starting from an empty collection
(i.e. one in which size = 0). Answer in terms of m (the number of operations) and n (the size of A).
Make your bound as tight as possible, and show your working.
c. [2 marks] Based on your answer to part (b) of this question, what is the amortised cost per INSERT
operation, over a sequence of m consecutive INSERT operations, starting from an empty collection?
Page 2 of 5
Semester Two Final Examinations, 2018 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 4 [25 marks]
The Bellman-Ford algorithm (with pseudo-code given below) solves the single-source shortest-paths
problem on a weighted, directed graph G with vertices G.V and edges G.E and weights w, as long
as there are no negative weight cycles. The algorithm returns TRUE if and only if the graph contains no
negative weight cycles that are reachable from the source vertex s. In that case the final shortest-path
weight from the source s to a vertex v is stored in v.d at the termination of the algorithm.
BELLMAN-FORD(G,w, s)
1 // G is the graph, w the weight function, s the source vertex
2 INIT-SINGLE-SOURCE(G, s)
3 // Relax each edge |G.V |−1 times to find shortest paths
4 for i = 1 to |G.V | − 1
5 for each edge (u, v) ∈ G.E
6 RELAX(u, v, w)
7 // Check for negative-weight cycles
8 for each edge (u, v) ∈ G.E
9 if v.d > u.d + w(u, v)
10 return FALSE
11 return TRUE
INIT-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ G.V
2 v.d = ∞
3 v.pi = NIL
4 s.d = 0
RELAX(u, v, w)
1 if v.d > u.d + w(u, v)
2 v.d = u.d + w(u, v)
3 v.pi = u
Consider the weighted directed graph G with vertices G.V = {a, b, c, d, e} and weight function
w = {(d, b) 7→ −4, (d, e) 7→ 1, (c, e) 7→ 1, (c, d) 7→ 1, (b, c) 7→ 2, (a, b) 7→ 1},
which maps the directed edges in G, G.E = domain(w), to values.
a. [6 marks] Show how the Bellman-Ford algorithm runs on graph G with weight-function w, using
vertex a as the source. You must assume that in the loop on line 5 of BELLMAN-FORD the edges are
always visited in the following order (from left to right):
(d, b), (d, e), (c, e), (c, d), (b, c), (a, b)
Give your answer by showing the values of v.d and v.pi for each vertex v ∈ G.V after each iteration
of the first for loop (line 4) in the BELLMAN-FORD algorithm. Also state whether or not the return
value of the algorithm will be TRUE or FALSE.
b. [4 marks] For which vertices v from G (if any) does there exist a negative-weight cycle on some
path from a to v?
c. [15 marks] Modify the Bellman-Ford algorithm, so that (instead of TRUE/FALSE) the return value
is the set of all vertices v in G.v such that there is a negative-weight cycle on some path from the
source vertex s to v. (If the return value is the empty set, this will mean that the graph contains no
negative weight cycles.)