Welcome back to uoeadspractice! This is going to be the seventh (two were missing) and last challenge, incorporating the remaining material. The problems will be:
1. Heuristics for Kruskal;
2. Kruskal; and
3. Convex Hull.
1. Heuristics for Kruskal
In order to implement Kruskal’s algorithm, one needs to have an implementation of Disjoint Sets. Thus the first task is to implement this data structure, together with some heuristics which make Kruskal run faster.
Your data structure needs to maintain a collection of disjoint sets and have three public methods (slide 6):
- makeSet(int x): creates a new set with only member x;
- union(int x, int y): joins the set containing x with the set containing y; and
- findSet(int x): returns the set containing x.
The DisjointSet data structure should be implemented as a forest, and the heuristics that need to be included are Union-by-Rank and Path Compression.
Union-by-Rank is attaching the tree of smaller rank to the one of higher tank, when joining two trees. Thus it should be part of the union method.
Path Compression is re-linking nodes during a findSet operation. All the nodes on the path from x to the root of its tree are re-linked as direct children of the root to increase lookup time for later lookups.
The algorithm of Kruskal for computing an MST is slightly odder, in my honest opinion. Nevertheless, it is a very beautiful and elegant algorithm and deserves to be implemented! Roughly put, it goes like this:
- Start with considering all vertices of the graph as separate connected components;
- Sort the edges of the graph by increasing weight;
- For each edge: if it is connecting two different connected components then add it to the MST
It takes longer to convince yourself that Kruskal is correct, but trust me – it is. Better still – read the slides (slide 5).
The complicated part of the implementation is implementing Disjoint Sets, but you already did this in problem 1, so it should be piece of cake now.
Graph kruskalMST(Graph graph);.
3. Convex Hull
The problem for finding a convex hull is maybe my favorite one in the course. It is a pity that it was not in the examinable material last year, but maybe you will have better luck and have an exam question on it!
So the problem is as follows: given a cloud of points, find the list of points lying on the convex hull of the cloud.
vector<pair<int, int> > convexHull(vector<pair<int, int> > points);
ArrayList<Point> convexHull(ArrayList<Point> points);
You should be able to wrap 106 points in less than a second.
How to Submit
After you’re done, put the functions in one file called winchal9.cpp or WinChal9.java. In case you are using Java, obviously you need a class. Call it WinChal9 and let it reside in a package called uoeadspractice.<nickname>.challenge9. Also, add a comment with your nickname in the beginning of the file.
When you’re done with that, send the file(s), together with a nickname, and optionally degree, year and university (if it is not University of Edinburgh) to uoeadspractice a t gmail d o t com. The deadline for submitting your code is Sunday 18 November 2012 2359 GMT.