Figure 1: Example of a planar graph
1 (33 marks) Graph Algorithms
In graph theory, a planar graph is one that can be drawn on a plane in such a way that no pair of edges cross each other. (They may, of course, share their end points). Figure 1 shows an example of a planar graph. It is a known fact that for any planar graph G with v vertices and e irreflexive edges, e ≤ 3v − 6 for v ≥ 3.
(i) [6 marks] Name two alternatives for the representation of graphs for the purposes of implementing graph traversal. Assuming you are only dealing with planar graphs, describe the space complexity of each representation solely as a function of v using big-O notation. Show your work.
(ii) [2 marks] Consider the task of representing a planar graph with 100,000 vertices. Which of the above two alternatives would require less space to represent such a graph and why?
(iii) [6 marks] Consider the task of graph traversal on the graph in Figure 1. Assuming you begin in vertex A, list, while preserving the order, the first 7 graph vertices that a breadth-first search would add to the search queue. In case the exact order of some vertices is under-specified by the algorithm, assume they are added in alphabetical order.
(iv) [6 marks] Consider the task of graph traversal on the graph in Figure 1. Assuming you begin in vertex A, list, while preserving the order, the first 7 graph vertices that a depth-first search would add on to the search stack. In case the exact order of some vertices is under-specified by the algorithm, assume they are added in alphabetical order.
(v) [6 marks] Consider Borůvka’s algorithm for finding the minimum spanning tree of a graph (see page 2).
Page 1 of 6 Continued.
Algorithm 1: Borůvka’s algorithm Borůvka(G)
Initialise spanning forest F to n single-vertex trees While (F has more than one tree)
foreachT inF,findthesmallestedgefromT toG−T add all selected edges to F , thus merging pairs of trees
Draw the minimum spanning tree produced by Borůvka’s algorithm for the graph in Figure 1. Preserve the relative layout of all vertices for the ease of marking.
(vi) [1 mark] How many times was it necessary to execute the While loop of the algorithm to produce the final result?
(vii) [1 mark] Name the last edge added to the minimum spanning tree by the algorithm.
(viii) [5marks] NameoneaspectinwhichBorůvka’salgorithmasdefinedhereisunder-specified or inaccurate and suggest a way to resolve it. Answer in no more than two sentences.
2 (34 marks) Algorithm Design Strategies
(i) [14 marks] I am quite missing my French cheese, and I have requested my family to send me a parcel full of cheese. Given the cost of postage, I want to maximise the value of the parcel. My family bought whole loaves of cheese, each loaf ci having a weight wi in grams and a price in pounds per kilogram pi . Given W , the maximum allowance in kilograms for a given parcel, and the ability to take an arbitrary amount of a given loaf of cheese (I just need to cut as much as I need), I would like to calculate the maximum possible value for my parcel.
For example, assume I am given three loaves of cheese, a Beaufort (3000g, £50/kg), a Comté
(2000g, £40/kg) and Tomme de Savoie (3000g, £30/kg), and a maximum weight allowance
for the parcel equal to 6 kg. As I am allowed to cut a portion of a loaf, the maximum value of
myparcelis3×50+2×40+1 ×3×30=260.Icanachievethemaximumvaluebytaking 3
the entire Beaufort, the entire Comté and a third of the Tomme de Savoie.
Amelie tells me she has a general algorithm that can optimise any parcel given a list of cheese loaves (with their weight and price per kg). In addition she can find the solution in O(n) where n is the number of cheese loaves. Her solution is to sort the cheese loaves by price per kilogram, from the most to the least expensive, then follow these steps:
1. Takethemostexpensivecheesethatremainsandaddittotheparcel.
2. Ifitdoesnotfitintheallowedweightlimit,takethelargestportionpossiblewithinit.
Page2of6
3. Repeatuntiltheparcelreachesthemaximumweightallowance.
In no more than 100 words, comment on the validity of the assertions made by Amelie, addressing the following questions:
(a) [7 marks] Does her approach always provide the optimal solution? If yes, provide an informal proof; if not, provide a counter example.
(b) [5 marks] Is the suggested complexity correct? If yes, explain why it is correct; if not, provide the correct complexity and justify your answer.
(c) [2marks] Whatisthetypeofstrategyusedbythealgorithm?
(ii) [20 marks] Having received my cheese, I thought it would be nice to have some wine with it. Again I have asked my family to send me some bottles of wine in a parcel. My family bought several bottles, each bottle vi containing a volume of wine qi in centilitres and having a price per litre pi. This time we cannot put a portion of a bottle in the parcel – either we put the whole bottle in or we don’t.
The quantity qi may differ from one bottle to another. For example a bottle of size “Chopine” contains 25cl while a “Melchior” contains 1800cl. For simplicity, we make the assumption that one litre of wine weighs one kilogram and we ignore the weight of the glass bottle. Again I would like to optimize my parcel to achieve the highest possible value in pounds (£) given a maximum allowance W in kilograms.
• Ameliestatesthatherprevioussolutionstillworksinthiscase,butinsteadofaddinga portion of a bottle, we discard the bottle and look at the next one. The complexity remains the same.
• Brendan disagrees and states that Amelie’s algorithm does not always work. He has a better solution that works all the time and is only slightly slower than Amelie’s even for a very large number of bottles and weight allowance. The idea is to compute all possible subsets of the set of bottles available, and take the subset with the highest value and a weight below the maximum allowance.
• Clémentine states that she has the best solution. It is much faster than Brendan’s solution, even in the worst case scenario. In addition, it always provides the optimal solution. Her algorithm is as follows:
Page 3 of 6 Continued.
Algorithm 2: Clémentine’s algorithm.
Function optimalPackageValue(bottles: List[Bottle], weight: int): double return pack(sort(bottles), weight); //sort bottles by price per kg
end
Function pack(bottles: List[Bottle], weight: int): double if bottles is empty: then //No more bottles to add
return 0; end
if weight ≤ 0: then //parcel already full return 0;
end
currentBottle = head(bottles);
maxValue = currentBottle.price + pack(tail(bottles), weight – currentBottle.weight); maxValue = max(maxValue, pack(tail(bottles), weight));
return maxValue;
end
Using less than 300 words (excluding any formulae), comment on the validity of the assertions made by each person, addressing the following questions:
(a) [10 marks] Does the solution always provide the optimal solution? If yes, explain why; if not, provide a counter example.
(b) [6marks] Isthecomplexitycorrect?Ifyes,explainwhyitiscorrect;ifnot,providethe correct complexity and justify your answer.
(c) [4marks] Whattypeofstrategy(ifany)isusedbythealgorithm?
3 (33 marks) Search in Dictionaries
Consider the following hash table, which uses open addressing, linear probing, and h(x) = 2x:
(i) [6 marks]
slotnumber 0 1234567 datakey 12 4 5 8 7
Listallpairsofkeys(Key1, Key2)forwhichyouarecertainthatKey1hasbeenentered into the hash table at some point in time before Key2 was added. Do not enter pairs that can
Page4of6
be inferred from other pairs, e.g. if you list (12,8) and (8,7), there is no need to list (12,7).
(ii) [6 marks] Show the state of the hash table after deleting key “4” and retrieving keys “7” and “8”.
(iii) [6 marks] Consider two implementations of a hash table, one that uses a self-balancing binary search tree for the elements with clashing data keys, and another, which uses a linked list for that purpose. Boris knows that each of these approaches has at most a linear worst case time complexity when searching for an element of the hash table. Help him prove the following statements or provide the correct answers and explain the reasoning on which they are based:
(a) [3marks] ThefirstimplementationhasO(1)worstcasetimecomplexity.
(b) [3marks] ThesecondimplementationhasO(n)worstcasetimecomplexity.
(iv) [15 marks] Consider graph H on Fig. 2.
Figure 2: Graph H
(a) [6marks] Isthisgrapharepresentationofavalidbinarymin-heapdatastructure? Answer the question by describing whether it meets each of the necessary conditions.
(b) [6 marks] Assume that graph V on Fig. 3 is a valid binary min-heap, and show the result of removing its root element by plotting the entire heap after this operation.
Page 5 of 6 Continued.
Figure 3: Graph V
(c) [3marks] Giveanexample(plotthecontents)ofabinarymin-heapcontaining7 elements, such that only one node of the original graph will be affected by root deletion. Point at the node in question.
End of examination paper
Page6of6