## 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