Today I finally managed to give out the prizes I have prepared:

Prizes for 0th, 1st and 2nd place.

Prizes for 0th, 1st and 2nd place.

There was one for Rimas, one for dbaltrus, and one for me, as I felt I deserved a price too (in addition to the kind and not-so-kind words of feedback).

I want to thank all who participated once again – I hope you found benefit in it. Also, I want to thank Dr Mary Cryan for her support and for advertising the blog during the lectures.

I wish you happy holidays and good luck on the exam!

Happy Hacking.

– Stan

Advertisements

Challenge 9 (and final) has finished. There were two submissions, with Rimas’s one being slightly more correct than that of dbaltrus. Still, thanks to both for participating. Here’s the updated scoretable:

Place Nickname C1 – C7 score C9 score Total
1 Rimas 79 % 300/300 82 %
2 dbaltrus 63 % 250/300 66 %
3 Andrew 16 % 14 %
4 spooky 15 % 13 %
5 svepe 14 % 12 %

So by this the practice experiment is over. Once again big thanks to all who participated and to all who were following the progress. Also, good luck on the exam when it comes.

Happy Hacking!

– Stan

P.S. There will be prizes for the most dedicated!

Here are my solutions to the last challenge: WinChal9.

It took me about 4 hours to code them just by looking at the challenge specification, while talking to a very communicative friend of mine and watching videos on the Internet. My point is that it would have taken you less, if you tried!

My solution for finding the convex hull is using Graham’s scan and the implementation is also very close to the one in the lecture notes, so nothing fancy here either.

I hope you enjoyed the problems. Await final results soon.

– Stan

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.

2. Kruskal

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:

  1. Start with considering all vertices of the graph as separate connected components;
  2. Sort the edges of the graph by increasing weight;
  3. For each edge: if it is connecting two different connected components then add it to the MST
  4. Done!

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.

Format:

Graph kruskalMST(Graph graph);.

3. Convex Hull

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.

Format:

C++:

vector<pair<int, int> > convexHull(vector<pair<int, int> > points);

Java:

ArrayList<Point> convexHull(ArrayList<Point> points);

Test range:

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.

Happy Hacking!

-Stan

Challenge 7 has finished. There were two perfect submissions. Here’s the updated scoretable:

Place Nickname C1 score C2 score C3 score C4 score C6 score C7 score Total
1 Rimas 200 / 200 280 / 300 270 / 300 280 / 300 300 / 300 79 %
2 dbaltrus 200 / 200 260 / 300 280 / 300 300 / 300 63 %
3 Andrew 200 / 200 16 %
4 spooky 360 / 400 15 %
5 svepe 260 / 300 14 %

I hope you enjoyed it. Await the next challenge soon.

Welcome to the challenge of week 7. It will be about Minimum Spanning Trees and a real world problem. Here is the list of tasks:

  1. Build a Graph;
  2. Implement Prim’s Algorithm for building an MST;
  3. Counting change.

Minimum Spanning Tree

1. Graph

This problem is roughly the same as the one in C6: design a Graph data structure. It turned out that you do a better job at this than me, so I will not give a skeleton implementation this time. Just bear in mind that your graph should not be directed, and should have weights associated with its edges.

It is important that your implementation is clear, and that method / field naming is helpful for determining the purpose of the corresponding method / field.

2. Prim

The first algorithmic part of challenge 7 is implementing Prim’s algorithm for finding a MST of a graph. It is the first thing that comes to mind when one puts the effort into designing such an algorithm: start from some random vertex and then greedily add the shortest available edges to your tree. You can get a more formal introduction from lecture slides 8-22.

Implement this algorithm, in the following format:

Graph primMST(Graph graph);

As usual it should be reasonably fast, so use a heap for the priority queue.

3. Counting change

Initially, I was planning to make you implement Kruskal, but then there wouldn’t be any space left for a nice practical challenge I have in mind! So Kruskal is postponed for next week and instead you get to solve the following problem that occurs to each of us, every day: in how many ways can you count your pennies. The problem originates from Project Euler problem 31.

Our version, however, would be the following:

Count the number of ways in which you can pay x pence, using an arbitrary amount of 1p, 2p, 5p, 10p, 20p, 50p, 1pound, and 2pound coins. The number x will be less than 105 and you should produce the result faster than I can blink (but have in mind that I can blink quite quickly). Oh, and please don’t precompute the answers 🙂

Here is the format:

long countChange(int x);

Hint: If you’re clueless you can first solve Problem 31 on Project Euler and then read the nice PDF they have there (it becomes available after you solve the challenge). After that it should be a breeze.

How to Submit

After you’re done, put the functions in one file called winchal7.cpp or WinChal7.java. In case you are using Java, obviously you need a class. Call it WinChal7 and let it reside in a package called uoeadspractice.<nickname>.challenge7. 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 04 November 2012 2359 GMT.

Happy Hacking!

-Stan

Hi again, folks. Two submissions for this week: dbaltrus’s and Rimas’s. Apart from the design of the DS being slightly confusing for both solutions, the algorithms worked fine.

Updated scoretable:

Place Nickname C1 score C2 score C3 score C4 score C6 score Total
1 Rimas 200 / 200 280 / 300 270 / 300 280 / 300 75 %
2 dbaltrus 200 / 200 260 / 300 280 / 300 56 %
3 Andrew 200 / 200 20 %
4 spooky 360 / 400 18 %
5 svepe 260 / 300 17 %

I hope you enjoyed it. Await the next challenge soon.