Semester Two Final Examinations, 2018
COMP4500/7500 Advanced Algorithms & Data Structures
This exam paper must not be removed from the venue
Venue
Seat Number Student Number Family Name First Name
____________________ ________ |__|__|__|__|__|__|__|__| _____________________ _____________________
School of Information Technology and Electrical Engineering EXAMINATION
Semester Two Final Examinations, 2018
COMP4500/COMP7500 Advanced Algorithms & Data Structures
This paper is for St Lucia Campus students.
Examination Duration:
Reading Time:
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.
120 minutes 10 minutes
For Examiner Use Only
Question Mark
Page 1 of 5
Total ________
Semester Two Final Examinations, 2018 COMP4500/COMP7500 Advanced Algorithms & Data Structures
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(n) + n(n + 1) 2
b. [5marks]T(n)=3T(n)+nlog n 42
Question 2 [10 marks] Given the recurrence T(n) = 1
T(n) = T(⌊n/4⌋) + T(⌊3n/4⌋) + n
for1≤n<8 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 2 3 4 5
ifsize==n
REARRANGE(A) / rearranges the elements of array A size = n/2
A[size] = x size = size + 1
If
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).
INSERT(x) is called when size < n then element x is inserted into the collection. Otherwise, if INSERT(x)
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 2 3 4 5 6 7 8 9
/ G is the graph, w the weight function, s the source vertex INIT-SINGLE-SOURCE(G,s)
/ Relax each edge |G.V |−1 times to find shortest paths fori=1to|G.V|−1
for each edge (u,v) ∈ G.E RELAX(u, v, w)
/ Check for negative-weight cycles foreachedge(u,v)∈G.E
if v.d > u.d + w(u, v) return FALSE
return TRUE INIT-SINGLE-SOURCE(G,s)
10 11
RELAX(u, v, w)
1 ifv.d>u.d+w(u,v)
2 v.d =u.d+w(u,v)
3 v.π = u
Consider the weighted directed graph G with vertices G.V = {a, b, c, d, e} and weight function w = {(d,b) → −4,(d,e) → 1,(c,e) → 1,(c,d) → 1,(b,c) → 2,(a,b) → 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):
for each vertex v ∈ G.V v.d = ∞
1
2
3
4 s.d=0
v.π = NIL
b. c.
(d, b), (d, e), (c, e), (c, d), (b, c), (a, b)
Give your answer by showing the values of v.d and v.π 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.
[4 marks] For which vertices v from G (if any) does there exist a negative-weight cycle on some path from a to v?
[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.)
The modified algorithm should have the same asymptotic time complexity as the current algorithm. Give clear pseudocode (including all algorithmic details) for the modified parts of the algorithm.
Page 3 of 5
Semester Two Final Examinations, 2018 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 5 [25 marks total]
There are n (where n > 0) players, p1, p2, · · · , pn, standing in a row, where the value of the ith player in the row, pi, is v[i] for i in 1, 2, · · · , n. Each of the players needs to be allocated to one of two possible teams. There is a process for allocating the players to the teams.
The coaches of the two teams take turns selecting a player for their team. In each turn, the coach taking the turn must select (and allocate to their team) either the first player in the row who has not yet been allocated to a team, or the last player in the row who has not yet been allocated to a team. For example, the first coach to take a turn may select either p1 or pn. The allocation process finishes when there are no unallocated players left.
The total value of the players allocated to a team is the sum of the individual values of the players allocated to the team. More generally, for any 1 ≤ i ≤ j ≤ n, the total value of the players from pi,pi+1,···pj allocated to a team is the sum of the individual values of the players from pi, pi+1, · · · pj who are allocated to the team.
Note that if the total value of the players from pi, pi+1, · · · pj allocated to one team is X, then the total value of the players from pi, pi+1, · · · pj allocated to the other team must be (jk=i v[k]) − X.
The goal of each coach is to maximise the total value of the players allocated to their own team (and hence minimise the total value of the players allocated to the other team).
The coach who takes the first turn wants to know the maximum total value of the players that they can allocate to their team, given that each coach always makes a selection that will result in the maximum total value of the players allocated to their own team.
This problem can be solved by dynamic programming.
a. [15 marks] Let M(i, j) be the maximum total value of the players from pi, pi+1, · · · , pj that could be allocated by a coach to their team given that (i) it is currently their turn, and (ii) the players in that range (i.e. pi,pi+1,···,pj) are the only ones (from the n players standing in row) who have not yet been allocated, and (iii) the other coach always makes a selection that will result in the maximum total value of the players allocated to their own team. The solution we seek is M (1, n).
Give a recurrence defining M(i,j) for 1 ≤ i ≤ j ≤ n.
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.
b. [10 marks] For the dynamic programming solution indicate in what order the elements of the matrix M corresponding to the recurrence should be calculated. As part of answering this question, give pseudocode indicating the evaluation order.
Page 4 of 5
Semester Two Final Examinations, 2018 COMP4500/COMP7500 Advanced Algorithms & Data Structures
Question 6 [10 marks total]
Below we describe two computer science problems. The clique problem
A clique C of an undirected graph G = (V, E) is a subset of the vertices of G such that for each pair of vertices u ∈ C and v ∈ C, if u ̸= v then u and v are directly connected by an edge in G.E. The size of a clique C is the number of vertices in the set C.
Given an undirected graph G = (V, E) and an integer k ≥ 1, the clique decision problem is to decide if G contains a clique of at least size k.
This problem is known to be NP-complete (assuming a standard encoding of inputs).
The weighted-clique problem
Given a clique C from an undirected graph G = (V,E), and an integer-valued weight function w that maps each edge in G.E to a corresponding integer-valued weight, the weight of clique C is the sum of the weights of the edges in G that connect vertices in C.
Given an undirected weighted graph G = (V,E) with integer-valued weight function w, and an integer c ≥ 0, the weighted-clique decision problem is to decide if G contains a clique of at least weight c.
a. [5 marks] Prove that the weighted-clique problem is NP-hard.
b. [5 marks] Show that the weighted-clique problem is NP-complete and clearly state any assump-
tions that you make.
END OF EXAMINATION
Page 5 of 5