COMP20007 Design of Algorithms

Workshop 7 Solutions

Tutorial

1. Negative edge weights Your friend’s algorithm might sound like a good idea, but it sadly won’t
cure Dijkstra’s algorithm of its inability to handle negative edge weights properly. Simply adding a
constant value to the weight of each edge distorts the length of paths differently depending on how
many edges they contain. Therefore the shortest paths found by Dijkstra’s algorithm in the modified
graph might not correspond to true shortest paths in the original graph.

As an example, consider the graph below.

C
1 1
A −5 B 3 D

The shortest path from A to D is A, B, C, D. However, when you add 5 to every edge, the shortest
path becomes A, B, D:

C
6 6
A 0 B 8 D

(Interestingly, however, a similar idea forms the basis of a fast all pairs, shortest path algorithm called
Johnson’s algorithm. See [Link] for details,
it’s an interesting read!)

2. Master Theorem Note for this question that comparing a and bd is the same as comparing
logb a and d.
n
(a) T (n) = 9T + n3 , T (1) = 1
3
We have a = 9, b = 3, d = 3 and c = 1. So logb (a) = log3 (9) = 2.
Also 2 < 3 = c, so the Θ(n3 ) is the dominating term. So T (n) ∈ Θ(n3 ).
n
(b) T (n) = 64T + n + log n, T (1) = 1
4
We have a = 64 and b = 4, so logb (a) = log4 (64) = 3.
Also, since n + log n ∈ Θ(n1 ), d = 1 < 3, so T (n) ∈ Θ(n3 ).
n
(c) T (n) = 2T + n, T (1) = 1
2
We have a = b = 2 so logb (a) = log2 (2) = 1. Also n ∈ Θ(n1 ) so d = 1 as well.
So T (n) ∈ Θ(nd log n) = Θ(n log n).
(d) T (n) = 2T n2 = 2T n2 + 0, T (1) = 1

Here a = b = 2 and nd = 0 so bd = 0 < 2 = a, thus we get Θ(nlog2 2 ) = Θ(n).

1
3. Mergesort Time Complexity Recurrence relation:
n n n
T (n) = T +T + Θ(n) = 2T + Θ(n)
2 2 2
where T (n) is the runtime of mergesort sorting n elements. The first T ( n2 ) is the time it takes to sort
the left half of the input using mergesort. The other T ( n2 ) is the time it takes to sort the right half.
Θ(n) is a bound on the time it takes to merge the two halves together.

Recall that the Master Theorem states that if we have a recurrence relation T (n) such that
n
T (n) = aT + Θ(nd ),
b
T (1) = c,

then, 
d if a < bd


Θ n

T (n) ∈ Θ nd log n if a = bd .



Θ nlogb (a) if a > bd


We can recognise that the mergesort recurrence relation fits the form required by the Master Theorem,
with constants a = 2, b = 2, and d = 1.
bd = 2 = a
so, by the master theorem, T (n) ∈ Θ(n log n).

4. Lower bound for the Closest Pairs problem We can use the closest pair algorithm from
class to solve the element distinction problem like so, where the output is a collection of elements
C = {c1 , . . . , cn } and the output is Distinct or NotDistinct:

function ElementDistinction(C = {c1 , . . . , cn })

P oints ← {(c1 , 0), . . . , (cn , 0)}
Distance ← ClosestPair(P oints)
if Distnace is 0 then
return NotDistinct
else
return Distinct

So, we can see that we can solve the element distinct problem using the closest pair algorithm. This
is called a reduction from element distinction to closest pair.
We know that ElementDistinction is Ω(n log n), and want to prove that ClosestPair is also
Ω(n log n).
We assume for the sake of contradiction that ClosestPair can be solved in a time complexity smaller
(i.e., asymptotically faster) that n log n. As we have exhibited (provided) a reduction from Element-
Distinction to ClosestPair then this must also give us an algorithm for ElementDistinction
which is asymptotically faster than n log n.
This contradicts the statement that ElementDistinction is Ω(n log n), and as a result our assump-
tion that ClosestPair can be solved in a time complexity smaller (i.e., asymptotically faster) that
n log n must be false.
Hence ClosestPair can not be solved in faster than n log n time, and is therefore Ω(n log n).