COMPUTER SCIENCE TRIPOS Part IA – 2016 – Paper 1
Algorithms (TMS)
(a) We consider the minimum spanning tree problem. For each of the following
three scenarios, which algorithm would you use for efficiency and what would
its running time be?
(i) Graph with V vertices, E = Θ(V
3/2
) edges with arbitrary weights in R.
(ii) Graph with V vertices, E = Θ(V (log V )
2
), where edges have already been
sorted according to their weights.
(iii) Graph with V vertices, E = Θ(V ) edges with arbitrary weights in
{0, 1, . . . , blog V c}.
[6 marks]
(b) What are the advantages and disadvantages of the Bellman-Ford Algorithm in
comparison to Dijkstra’s Algorithm? [4 marks]
(c) For the graph with source vertex s below, perform Dijkstra’s Algorithm. It is
sufficient to state the order in which the four vertices are extracted from the
priority queue as well as their actual distances from the source s.
s u
v w
5
6
10
4
1
2
[6 marks]
(d) Suppose that we are given a weighted, directed graph G = (V, E) in which
edges that leave the source vertex s may have negative weights, but all other
edge weights are non-negative. Does Dijkstra’s Algorithm correctly find the
shortest path distances from s? Either give a proof of correctness or provide a
counter-example. [4 marks]