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.
Model Answer:
• Use a linked list to hold the elements of each set, and maintain a record of how many elements each set contains.
• Maintainanarraythatprovidesamapfromeachelement(vertex)tothe linked list for the set that it belongs to.
• The Find operation takes an element (vertex) as input and based on the mapping in the array, returns a pointer to the list that that element cur- rently belongs to.
• When the Find operation returns the same pointer for two different ver- tices then they are in the same set.
• The Union operation takes two elements (vertices) that are in different sets as input and merges their two sets. Suppose are merging (taking the union of) the sets for the two elements (vertices) u1 and u2. Look up, in the array, the list (pointer) for u1’s set, say p1 and the list for u2’s set, say p2. Note, we can assume that they belong to different sets, i.e.
Program Analysis Term 1, 2015
that p1 ̸= p2. For reasons that will become clear when we look at the efficiency of the Union operation, we will always merge the smaller list into the larger list. So suppose that p1 is the larger (or equal sized) set - this is why we maintain a record of how large each set is. We perform the union by stepping down the elements of the list p2 (the set that u2 belongs to) and for each element v in this set, update the entry for v in the array so that it points to p1 rather than p2, and add v into the list p1. It can be inserted at the front of the list since the order is not important. Furthermore, as elements are added to p1 increment the record of its size.
(b) Given your proposed implementation, how efficient are each of the opera- tions?
Model Answer:
• The Find operation is constant time since it involves looking up a value in an array.
• The efficiency of the Union operation is Θ(m) where m is the size of the smaller of the two sets being merged.
(c) What is the total running time of all the Union operations that arise during a run of Kruskal’s MST algorithm?
Model Answer: Suppose that the graph contains n vertices. The step that inserts elements into linked lists is the one that determines the running time of the Union operation, so we will focus on determined the total number of times this occurs during an execution of the algorithm. It turns out that we can give an upper bound on how many times a specific vertex will be inserted into some list. The key observation is that when copying a vertex into a new set, the size of the new set must be at least twice as large as the set it was previously in. We know this because we always copy elements of the smaller set into the larger set. Because the set that is produced at the end of the algorithm has n elements, the upper bound on the total number of times a particular vertex can be copied into a new set is O(log n). Since there are n vertices, the total number of times any vertex is added into any linked list throughout the run of the algorithm is O(n log n).
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.
Model Answer: The greedy method would be appropriate because it is possible to build an optimal selecting by selecting film showings one at a time working through the day.
(b) Giveanalgorithmthatsolvesthisproblemusingtheproblemsolvingmethod you have given in answer to Question 2a .
Model Answer: A effective algorithm would order film showings in a pri- ority queue in order of finish time, earliest to latest. Beginning with the time of day being the start of the day, at each iteration of the algorithm, the high- est priority film showing in the priority queue would be considered, if its start time is not before the current time of day then it is selected and the time of day up dated to the end time of that showing, otherwise that film showing is not selected.
(c) WhatistherunningtimeofthealgorithmyouhavegiveninanswertoQues- tion 2b?
Model Answer: The worst-case running time of the algorithm is O(n log n) time where n is the number of film showings, since this is the time it takes to create the priority queue and remove up to n times from it.
(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
Model Answer: The modified problem cannot be solved with the greedy method. Consider an extreme example with just two film showings: one beginning at the start of the day an running for just 10 minutes, and a second an extremely long film that begins 5 minutes after the start of the day and runs until the end of the day. The above strategy would select just the short film showing which is clearly not optimal.
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.
Model Answer: This is false. Let G have vertices { v1, v2, v3, v4 } with edges between each pair of vertices, and with the weight on the edge from vi to vj equal to i + j. Then every tree has a bottleneck edge of weight at least 5, so the tree consisting of a path through vertices v3, v2, v1, v4 is a minimum bottleneck tree. It is not a minimum spanning tree, however, since its total weight is greater than that of the tree with edges from v1 to every other vertex.
(b) Is every minimum spanning tree of G a minimum-bottleneck tree of G? Prove or give a counter-example.
Model Answer: This is true. Suppose that T is a minimum spanning tree of G, and T ′ is a spanning tree with a lighter bottleneck edge. Thus, T con- tains an edge e that is heavier than every edge in T′. So if we add e to T′, it forms a cycle C on which it is the heaviest edge (since all other edges in C belong to T′, it forms a cycle C on which it is the heaviest edge (since all other edges in C belong to T′). By the Cut Property, then e does not belong to any minimum spanning tree, contradicting the fact that it is in T and T is a minimum spanning tree.