COMPUTER SCIENCE TRIPOS Part IA – 2017 – Paper 1
Algorithms (DJW)
(a) Consider a directed acyclic graph with V vertices and E edges.
(i) What is meant by a total order on the vertices consistent with the edges?
[2 marks]
(ii) Describe an O(E + V ) algorithm to compute such a total order. [3 marks]
(b) Consider a directed graph with non-negative edge costs and with a given start
vertex s.
(i) Dijkstra’s algorithm computes distances from s to every other vertex. Give
psuedocode for Dijkstra’s algorithm. [4 marks]
(ii) Dijkstra’s algorithm can be implemented using a Fibonacci heap. State
the complexity of using this implementation. Justify your answer carefully.
[Note: Your answer should include mention of amortized costs.] [4 marks]
(c) Consider a directed acyclic graph with non-negative edge costs and with a given
start vertex s.
(i) Devise an algorithm to compute distances from s in O(E +V ) time. Justify
why your algorithm is correct. [4 marks]
(ii) Explain, with an example, why Dijkstra’s algorithm might take Ω(V log V )
time. [3 marks]