COMPUTER SCIENCE TRIPOS Part IA – 2014 – Paper 1
Algorithms (TMS)
(a) Given any directed graph G = (V, E) with non-negative edge weights, consider
the problem of all-pairs shortest path (APSP). Give the asymptotic runtimes of
the following four algorithms when applied (directly or iterated) to the APSP
problem as a function of |V | and |E|, and provide a brief justification for your
answer: Bellman-Ford, Dijkstra, matrix multiplication and Johnson. [8 marks]
(b) Consider the problem of converting currencies modelled by a directed graph
G = (V, E) with |V | vertices representing currencies and |E| directed edges
(u, v) each of which has a strictly positive weight w(u, v) > 0 representing
the exchange rate. For instance, for any real number x, we have x USD =
w(dollars, pounds) · x GBP. Our goal is, given a pair of currencies s, t ∈ V , to
find the least expensive way of exchanging from s to t, possibly by using more
than one exchange.
(i) How could you transform the graph by reweighting the edges so that the
problem could be solved with a shortest path algorithm? Indicate which
shortest path algorithm is used. [8 marks]
(ii) How would you deal with negative-weight cycles if they occurred in the
transformed graph? Give the perspective of the currency trader as well as
that of a computer scientist. [4 marks]