Explain what is meant by the translation strategy
Give an algorithm to compute all costs achievable by Pareto efficient paths from s to every other vertex
March 20, 2023Define unambiguous pre-order, in-order and post-order representations
March 20, 2023Explain what is meant by the translation strategy
COMPUTER SCIENCE TRIPOS Part IA – 2021 – Paper 1
Algorithms (djw1005)
This question is concerned with connected undirected graphs in which each edge has
a weight, and with spanning trees in such graphs.
(a) Explain what is meant by the translation strategy, and outline briefly the steps
of a translation-based proof of correctness. [3 marks]
(b) Give an algorithm for finding a maximum spanning tree, that runs in O(E +
V log V ) time. Explain why your algorithm’s running time is as required.
[8 marks]
(c) Prove rigorously that your algorithm is correct. [9 marks]
[Note: You may refer to algorithms from lecture notes without quoting the code. You
may use results from lecture notes without proof, but you must state them clearly.]
