COMPUTER SCIENCE TRIPOS Part IA – 2015 – Paper 1
Algorithms (TMS)
(a) Consider the two standard representations of directed graphs: the adjacency-list
representation and the adjacency-matrix representation. Find a problem that
can be solved more efficiently in the adjacency-list representation than in the
adjacency-matrix representation, and another problem that can be solved more
efficiently in the adjacency-matrix representation than in the adjacency-list
representation. [4 marks]
(b) Prove or disprove (by giving a counter-example) the following claim: If a directed
graph G contains a path from a vertex u to a vertex v, then any depth-first search
must result in v.d ≤ u.f, where .d is the discovery time and .f the finishing time.
[4 marks]
(c) We are given an undirected, connected graph G = (V, E) with edge-weights
w : E → R
+ and a minimum spanning tree T of G. How would you update
your minimum spanning tree T in each of the following three cases? Specify the
runtime of your algorithm and give a proof that the returned tree is indeed a
minimum spanning tree.
(i) We increase the weight of an edge e which is not in T. [3 marks]
(ii) We decrease the weight of an edge e which is in T. [3 marks]
(iii) We add a new edge e with weight w(e) to G. The weight w(e) is arbitrary,
but for simplicity you may assume that after adding the edge e no two
edges in G have the same weight. [6 marks]