Program Analysis Term 1, 2015 Problem Sheet 6
1. TheUnion-FinddatastructureisusedinKruskal’sminimumspanningtreealgo- rithm (reproduced below). In general, Union-Find is used when we are working with partitions of a collection of elements. In this case all of the sets (partitions) are disjoint: i.e. they do not share any elements.
This data structure is associated with the following two operations:
• a Find operation that determines which set an element is in, and can be used to determine whether or not two elements are in the same set; and
• a Union operation that combines the elements of two sets together into the same set.
Kruskal(G, w) :
let Q be the edges in E ordered by increasing weight initialise E′ to be the empty set
for each vertex v ∈ V
let C(v) be the singleton set containing v while |E′| < |V | − 1
remove edge { u, v } from Q if C(u) ̸= C(v) then
include { u, v } in E′
C(u) ← C(v) ← C(u) ∪ C(v) return E′
(a) Describe how the Union-Find data structure can be implemented in an effi- cient way.
(b) Given your proposed implementation, how efficient are each of the opera- tions?
(c) What is the total running time of all the Union operations that arise during a run of Kruskal’s MST algorithm?
Program Analysis Term 1, 2015
2. Your friend works at a large cinema complex with multiple screens each one showing a variety of different films during the day. She is the most senior projec- tionist at the cinema and each morning she is given the first opportunity to select the film showings that she is going to be responsible for that day. She can only look after one film showing at a time, and is paid £20 for each one she does.
Because the cinema complex has so many screens and the films it shows are so variable in length, your friend would like your help in making a selection that will maximise her income.
(a) What is an appropriate problem solving method to use in solving the prob- lem of maximising your friend’s income? Justify your choice.
(b) Giveanalgorithmthatsolvesthisproblemusingtheproblemsolvingmethod you have given in answer to Question 2a .
(c) WhatistherunningtimeofthealgorithmyouhavegiveninanswertoQues- tion 2b?
(d) Explain, by means of an example, why it would not be possible to employ the problem solving method you have given in answer to Question 2a if the scenario was altered so that instead of getting a flat fee for each film showing, your friend was paid 20 pence for each minute of a film showing that she was responsible for?
Program Analysis Term 1, 2015
3. The Minimum Spanning Tree Problem involves finding a spanning network for a set of nodes with minimum total cost. Here we explore a different objective: designing a spanning network for which the most expensive edge is as cheap as possible.
Specifically, let G = (V,E) be a connected graph with n vertices, m edges, and positive edge costs that you may assume are all distinct. Let T(V,E′) be a span- ning tree of G; we define the bottleneck edge of T to be the edge of T with the greatest cost.
A spanning tree T of G is a minimum-bottleneck spanning tree if there is no spanning tree T ′ of G with a cheaper bottleneck edge.
(a) Is every minimum-bottleneck tree of G a minimum spanning tree of G? Prove or give a counter-example.
(b) Is every minimum spanning tree of G a minimum-bottleneck tree of G? Prove or give a counter-example.