So, what have I been up to lately…
Well, I’ve done various stuff — Jérémy and I have made the first third of the mandatory assignment in dADS. It’s actually an interesting assignment: we have to design an algorithm that will find the maximum matching in a bipartite graph. The first thing we had to do, was to prove that an algorithm written in pseudo code was valid and correct. The algorithm uses a transition system to color the nodes in the graph, so we had to prove a couple of things about that too.
This week we have to design efficient datastructures that will allow us to color the graph using the transition system in time O(m+n) where m is the number of edges in the graph and n in the total number of vertexes. We will use these datastructures in the final third of the assignment where we have to implement the algorithm in Java. Exciting stuff…
I plan to publish the report here at gimpster.com when we’re finished, so stay tuned. (It’s in Danish, so don’t be too excited if you cannot read that :-)
Leave a comment