=[laiAdvanced Algorithms & Data Structures November 8, 2018
The University of Queensland COMP4500/COMP7500
Dr Larissa Meinicke 2018, Semester 2
[Exam Paper]
Question 1. Recurrence Relations [10 marks] (2 parts)7
• [5 marks]
• [5 marks]
Solution:
•
WTP: n(n + 1) = O()
Need c, s.t. For all
So suffices n(n + 1) = O()
Applying master’s theorem:
A = 8; b = 2
, where e = 1 > 0.
So by the master theorem’s case 1, T(n) = Θ() = Θ()
b) T(n) = ， a = 3, b = 4
where e > 0
So by the master theorem’s case 3, T(n) = Θ()
Question 2. Recurrences – Substitution Method [10 marks]
WTP: T(n) = O(n lgn)
Need c, > 0 s.t. For all n >= , 0 <= T(n) <= cn lgn
Base case:
Try = 1
T(1) = 1 > c1 lg1
Try = 2
No n >= 2 directly dependent on T(1) and:
T(2) = 1 <= c2 lg2 if c >= 1
Inductive step:
assume inequality holds for T(floor(n/4)) and for T(floor(3n/4))
T(n) <= cn lgn <= [(cn)/4 lg(n/4)] + [(3cn/4) lg(3n/4)] + n <= cn/4(lgn - lg4) + 3cn/4(lg3n - lg4) + n <= cn lgn/4 - 2cn/4 + 3cnlg3n/4 - 6cn/4 + n <= cn lgn/4 - 8cn/4 + n + 3cn/4(lg3 + lgn)0 <= cn lgn/4 - 2cn + n + 3cn lg3/4 + 3cn lgn/4 <= cn lgn - (2cn - n - 3cn lg3/4) <= cn lgn if 2cn - n - 3cn lg3/4 >= 0
2cn – n – 3cn lg3/4 >= 0
Let n = 2, c = 4
2 . 4 . 2 – 2 – (3 . 4 . 2 lg3/4) >= 0
14 – 6 lg3 >= 0
lg3 < 2
14 - 6 . 2 >= 0
14 – 12 = 2 >= 0
So = 2 and c = 4 will suffice.
Question 3. Amortised Analysis [20 marks] (3 parts)
I got ceil( (m – n)/2 )?? Or floor( (m – n – 1) / 2) -1
Not sold on these answers? My thinking is this:
Let A have size 8 (could be any power of two), so n = 8
Start with empty array so size = 0
Perform first insert operation with x = 1:
A = [1]
Size = 1
Fill the rest of the array with 2, 3, 4, 5, 6, 7, 8
A = [1, 2, 3, 4, 5, 6, 7, 8]
Since size is incremented after an element is added, we fully fill the array and finish with size = 8
The next call to insert results in half the array being deleted since size == n.
Assume for now that rearrange does nothing.
A = [1, 2, 3, 4] & size = 4
(Technically A is still [1, 2, 3, 4, 5, 6, 7, 8] since we don’t actually delete the elements but rather reset the cursor of the list to override from n/2 but for demonstration I will leave it as half the array).
Therefore at the 9th operation m, we have our first call to REARRANGE (the second line of the function)
Since we now have half the array, we insert the new element.
A = [1, 2, 3, 4, 9] & size = 5
Note that this still occurs at m = 9.
You should see now that 10, 11, 12 will all be inserted normally without rearranging to reach:
A = [1, 2, 3, 4, 9, 10, 11, 12] & size = 8
The next insert again calls rearrange so at m = 13 we have called rearrange twice.
Extending this out:
m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#Rearrange
0
0
0
0
0
0
0
0
1
1
1
1
2
2
2
2
3
Which gives the function:
0 for m <= 8 for m > 8 (+3)
I have another solution: t = ceiling(2(m-n)/n) for m > = n. I think it returns the same value t when m is an integer. Please let me know if I read the question wrong.
Not sure if right:
Time to insert is: * n
Making it roughly O(n^2)
O(n^2) / n operations makes it O(n) using aggregate method. For example m = 5,000,000 and n = 100. The value converges to O(1) < m < n, O(n^2) when m <= 4n + 1 and O(n) when m > 4n + 1
Another solution:
for m > n
(how did you get rid of n? I think O(m) is not tight enough)
I got:
The costs of line 1, 4, 5 are 3
3m + floor(2(m-1)/n – 1) *
<= 3m + [2(m-1)/n - 1] * cn
= 3m + c*(2m - 2 - n)
= (3+2c)m - cn -2c
= O(m - n)
Anyone can tell me if I am wrong?
O(n) (-2)
If the answer to (b) is ,
I think O(1) looks legit, i’m thinking from the accounting method perspective; if an array has size=n, then all n elements will be rearranged everytime we want to insert an element into a full array (and it is possible for an element x to be in the array since day 1 and be rearranged for all m insertions bc it coincidentally always ended up in the first half of the array). This means for each insert, they should be charged extra to cover (1) itself, and (2) for the existing half of the array to be rearranged when the array is full again. So each insert should have an amortized cost of 2 (from the nth insert onwards i guess, the first 4 can have a cost of 1 LOL idk if any of this makes sense it’s almost 3am) which is thereforeO(1).
Question 4. Graphs [20 marks] (1 part)
It would be smart to draw the graph out.
Iteration 1:
e.d=∞, e.𝜋=NIL; d.d=∞, d.𝜋=NIL; c.d=∞, c.𝜋=NIL; b.d=1, b.𝜋=a; a.d=0, a.𝜋=NIL
Iteration 2:
b.d=1, b.𝜋=a, e.d=∞, e.𝜋=NIL; d.d=∞, d.𝜋=NIL; c.d=3, c.𝜋=b; a.d=0, a.𝜋=NIL
Iteration 3:
b.d=1, b.𝜋=a, e.d=4, e.𝜋=c; d.d=4, d.𝜋=c; c.d=3, c.𝜋=b; a.d=0, a.𝜋=NIL
Iteration 4:
b.d=0, b.𝜋=d, e.d=4, e.𝜋=c; d.d=4, d.𝜋=c; c.d=2, c.𝜋=b; a.d=0, a.𝜋=NIL
Iteration 5: to be pedantic: Bellman-Ford doesn’t set distances during the final iteration. It just returns False as soon as an edge could be relaxed. So the states of the vertices after iteration 4 will be the same as after iteration 5.
b.d=0, b.𝜋=d, e.d=4, e.𝜋=c; d.d=3, d.𝜋=c; c.d=2, c.𝜋=b; a.d=0, a.𝜋=NIL
THis shouldn't be updated in iteration 5 then??
-> Yup, only need to relax |V| – 1 times
Returns FALSE
Vertices: b, c, d – what about e? ( a => b => c => d => b => c => d )
It’s a negative cycle at the second b loop.
Maybe b c d but Wikipedia says a path should only contain distinct/repeated points.
7 S = {}
8 for i = 1 to |G.V| – 1
9 for each edge (u, v) in G.E
10 if v.d > u.d + w(u, v)
11 S.add(v) // Because set contains unique vertices, add() will only add if v not in S
12 return S
(but it says: the return value is the empty set if the graph contains no negative weight cycles, should this be:
7 S = {}
8 for i = 1 to |G.V| – 1
9 for each edge (u, v) in G.E
10 if v.d > u.d + w(u, v)
11 S.removeAll()
12 return S
13 return S
)
Other answer:
(Outer loop unnecessary, and source vertex should also be added to the set) +1
7 S = {}
8 for each edge (u, v) in G.E
9 if v.d > u.d + w(u, v)
10 S.add(u)
11 S.add(v)
12 return S
I am afraid these answers above does not include vertex b in the solution set.
Question 5. Dynamic Programming [25 marks] (2 parts)
See Problem 8 here for similar problem solution: http://courses.csail.mit.edu/6.006/oldquizzes/solutions/final-f2009-sol.pdf#page=12
• You want to
M(i, j) = // Need init step
For 1 < i < n-1
For i % 2 <= j <= n
v[i] , if i = j
0 , if i > j
max(v[i] + M(i + 1, j), v[j] + M(i, j – 1)) , if i < j <= n
MaxValue(v):
// Build array
M[v.length][v.length] // First choice
N[v.length][v.length] // Second choice
For i < n:
M[i][i] = v[i]
N[i][i] = 0
For l <= n:
For i <= n - l + 1:
j = i + l - 1
If N[i + 1][j] + v[i] < N[i][j - 1] + v[j]:
M[i][j] = N[i][j - 1] + v[j]
N[i][j] = M[i][j - 1]
Else:
M[i][j] = N[i + 1][j] + v[i]
N[i][j] = M[i + 1][j]
Return N(1, n)
Question 6. Reductions [10 marks] (2 parts)
• [5 marks] Prove that the weighted-clique problem is NP-hard.
Do u agree with below?
Reduce NPC problem to our new Problem eg. use clique to solve weighted-clique
Weighted Clique(G, w, c):
for i = 1 to |G.V|
C = Clique(G, i) // Check if we have a clique
weight = 0
for j = 1 to |C.V|
for z = j + 1 to |C.V|
weight += w[C.E[C.V[ z ], C.V[ j ]]]
if weight >= c
return true
Alternative answer:
If we set w=1 for all edges, and c=k, the weight-clique problem is reduced to the clique problem, which we know is NP-hard. ∴ The weighted-clique problem is also NP-hard.
• [5 marks] Show that the weighted-clique problem is NP-complete and clearly state any assumptions that you make.
Do u agree with below? +1
Above we have proven weighted clique is NP-Hard.
We must now show it is within NP, that is, there exists a polynomial time way to verify an answer.
So given a Clique, the graph, weights and target c, we must: 1. Check that all Vertices in Clique are connected to each other 2. Check that the sum of the edges between all vertices is not less than c
END OF EXAMINATION