COMPUTER SCIENCE TRIPOS Part IA – 2020 – Paper 1
Algorithms (djw1005)
We are given a directed graph g = (V, E). A vertex v ∈ V is said to be an origin if
for any other vertex w ∈ V there is a directed path from v to w.
(a) Consider the dfs recurse(g,s) algorithm as described in lecture notes. Show
carefully that, once it terminates, if it has visited a vertex v then it has also
visited all vertices reachable from v. [4 marks]
(b) Suppose g has an origin. Give an algorithm that returns an origin, and which has
O(V + E) running time. [Hint: Consider dfs recurse all(g). What happens
after it visits an origin?] [5 marks]
(c) Suppose g has an origin. Prove that the vertex returned by your algorithm in
part (b) is indeed an origin. [6 marks]
(d) Give an algorithm that returns all origins, and which has O(V + E) running
time. If the graph has no origins, your algorithm should return an empty set.
Explain briefly why your algorithm is correct. [5 marks]