Coffee + graphs

Good morning!

Today I kick off with some more Algorithms basic theory. Tim Roughgarden, the instructor, has a precise yet captivating delivery style (not too informal, not too nerdy), which makes this worthwhile.
In general, I noticed the same pattern during all of my studies: the instructor has a large responsibility in keeping the students’ heads up, in both senses.
The presentation of even the most formal of subjects has to be enriched by “refreshing” elements. For example, my Calculus 1, 2, 3 AND 4 teacher, the never-enough-celebrated G. C. Barozzi, had a way of embedding anecdotes and biographical facts about mathematicians. This both put the subject in historical context, making it feel less abstract, and relieved the audience from continued focus. Seems too nerdy still? You’ve found the wrong blog then! Ha.

I can agree that some subjects might feel a bit “dogmatic”, as formal proof of all their aspects would require a disproportionate effort from large part of the audience. In this case, it is up to the lecturer to select the more illuminating material beforehand : Longum iter est per praecepta, breve et efficax per exempla (Seneca)

So, contraction algorithms for the MINCUT problem for graphs: given a graph G = \{V, E\}, with nodes V and edges E, which is the smallest set of edges \tilde{E} that divides G in two otherwise disjoint subsets of nodes V_1 and V_2 (i.e. the smallest cutset)?

Random contraction (Karger’s algorithm)
Sequentially remove edges uniformly at random, merging the resulting nodes V(E_{k}) = V_i, V_j \rightarrow V_i (“edge contraction”) and rerouting the edges initially connected to V_i and V_j to V_i.
The cutset that remains when there are only two nodes left is a local optimum of MINCUT.
karger_random_graph_contraction
A single run of Karger’s algorithm (adapted from Wikipedia)

If N_E = |E| is the edge set size, there are N_E! possible contraction sequences. Only a subset of these yield the true MINCUT (i.e. the problem is path-dependent).

Catching up

August 23, 2011

As I see now, I’ve been a very irresponsible blogger, leaving what was intended to be my latest online brainchild in the dust of oblivion for more than two years.
Not that I feel that guilty about this: I didn’t have anything worthy to share with the amorphous and faceless internet crowd.
Call it a very refined sense of self-censorship, as opposed to the easy trigger of too many compulsive self-elected online opinionists.

This post serves then to mark the end of an era of my life and the beginning of a new one: after obtaining my M.Sc.EE from DTU Fotonik (DK), I will move on to starting a Ph.D. in the Netherlands.

I’ll keep you (sort of) posted,

saturday morning

January 31, 2009

Chinese flower tea

flower tea from inner China, kindly shared by Jiayuan,

listening to DroneZone

and reading the Feynman lectures on physics, vol.3.

Pure bliss.