On plant growth and form
September 28, 2013
How quickly does the number of leaves on this plant increase, and why?
The photo above is of a Schlumbergera truncata (or “Christmas cactus”), which my mother (from whom I got the parent plant) calls “Woman’s tongue”. The latter might be seen as a rather sexist definition (pointy and forked..) but I guess it’s an old heritage, from when the world was younger..
Anyway, how fast do the leaves increase in number, and what drives the general form of the plant?
Say we have initially N branches, each that can generate one to three leaves (branching factor p), more or less at random.
If the branching factor were constant and identical for all branches, after one generation we would see 2N to 4N leaves; after two, 3N to 16N, or, for the jth branch: .
The number of leaves at each level i is seen to be where the bound constants are and .
In the real world, a branch has spatial extent, with each leaf occupying a volume, with no intersections or overlaps in . Moreover, the leaves seek and thrive in sunlight (phototropism), which conditions their orientation and size.
Therefore we could represent a plant as a vector field, with “streamlines” (nutrient direction) and “polarization” (orientation to sunlight).
Gravity, through the selfweight loading of the branches and capillary diffusion of nutrients, obviously plays a part.
We can sketch the processes at play in the following, informal manner. First some notation: for leaf k of level i, the leaf size , orientation , sunlight exposure (intensity flux) , viability (function of exposure and distance from the root) , repulsion potential (function of size and distance to nearest leaf neighbors) , branch node stiffness , which increases as the leaf matures.
Moreover we can define the branch vitality as the sum over all the parent leaves (viability upstream).
(leaf size influences exposure, repulsion and stiffness)
(exposure, viability and stiffness influence leaf size, viability and leaf angle)
(repulsion influences exposure through position: model requires collision and raytracing, which require considerable computational effort)
, but also
As each leaf matures, it becomes larger in size, stiffer and possibly its exposure efficiency reaches a plateau.
Recursive algorithms
September 14, 2013
A recursive algorithm calls itself with a subset of the initial data until its base case is reached (e.g. data cannot be split further).
The canonical example is the factorial operation: .
A straightforward Python function that implements this idea follows:
def fact(x): if x <= 1: return 1 else: return x*fact(x1)
In practice, recursion actually can speed up the execution of divideandconquer (DNQ) algorithms (i.e. in which the initial problem is sequentially split in more manageable subproblems), as discussed in the next section.
Analysis: the Master Theorem
An asymptotic estimate of the running time of a recursive DNQ algorithm with deterministically equal size subproblems is given by the following formula: , where is the data size, and are the number of recursive calls per level (i.e. the branching factor of the recursion tree) and the associated reduction in input size, and describes the computational effort associated with preprocessing (i.e. all that is done before the recursions begin).
One can then identify three cases (for simplicity, is assumed to be a power of ):
 If then
 If then
 If then
This week in science, technology, public policy
September 11, 2013
 Open source lab tools
Scientific instrumentation tends to be expensive: the long r&d&calibration cycles necessary to produce a precise and reliable tool have a direct impact on prices. However, there is a growing number of initiatives that aim to distribute or sell lowcost, “open” tools/techniques, e.g. http://www.openbiotech.com, http://publiclab.org.
Will openness foster science education and proliferation, specifically in places that cannot afford branded machinery? Is lowcost an observerindependent synonym for lowquality? where quality might mean any combination of reproducibility, availability of debug/maintainance support, etc.

The order of things ; what college rankings really tell us – M. Gladwell
Not exactly news, but this piece from the New Yorker explores how various – arbitrary – choices of metrics used to rank higher education institutions (e.g. graduation rate, tuition etc.) lead to very different results.
This would not be of much consequence, if these charts were not routinely touted as authoritative by the school deans themselves, and used in all media to bias the perception of “excellence”.

NSA: Possibly breaking US laws, but still bound by laws of computational complexity – S. Aaronson
Scott Aaronson argues that the most widely used “attacks” on citizens’ privacy are the most straightforward (“sidechannel”, e.g. lobbying either the standardization committees to put forward weak encryption protocols or commercial software vendors to plant backdoors in their network services) and do not involve disproving mathematicallyproven techniques. Social engineering, old as security itself.
Bruce Schneier, a prominent security expert, gives a few practical tips to have a better illusion of online privacy.
Last but not least, XKCD’s analysis is ever so accurate:
(embedded from http://xkcd.com/1269/ )
Area – Giro giro tondo (live 1977)
August 31, 2013
Area were an Italian progressive rock band, until the premature death of their frontman, Demetrio Stratos.
I find the sheer creativity and sense of freedom conveyed by their sound to be so refreshing.
Below, one of their albums. Enjoy!
Percolation threshold estimation
August 30, 2013
The first assignment for Algorithms 1 is an estimation for the percolation threshold in an nbyn array of sites; the system is said to percolate whenever there exists an uninterrupted series of connections between the top “edge” and the bottom one.
We need a fast lookup for the neighborhood of any given site; the neighbors() method checks whether a site is in the middle or on the sides or corners of the grid:
def neighbors(ii, n): "returns list of neighbors of ii in nbyn grid" l = [] if mod(ii, n) > 0: l.append(ii1) if mod(iin+1, n) > 0 or ii == 0: l.append(ii + 1) if ii > n1: l.append(ii  n) if ii < n*(n1): l.append(ii + n) return l
I use two lists: L is a pointer array as in the previous post and O contains the state tags (‘#’ for closed, ‘.’ for open site). There are two extra sites, serving as roots for the top, resp. bottom sites.
def percolation_frac(L, O, sites): for ii, isite in enumerate(sites): O[isite] = '.' if isite < n: L[isite] = ridxTop elif n*(n1) < isite <= N: L[isite] = ridxBot neighb = neighbors(isite, n) for inb in neighb: if O[inb]=='.': L = wqupc2(L, isite, inb) if L[1]==L[2]: """ percolation: top and bottom virtual sites belong to same component """ pf = float(ii) / N return pf
As there is no analytical means of predicting when the percolation phase transition is going to occur, we just run the experiment in Monte Carlo mode (many times with randomized initialization), and average the perrun percolation threshold estimate.
Theory tells us that in a square lattice, this value lies around 0.5927 .
My implementation bumps into a few false positives, possibly due to the order in which the union operation is performed, thereby skewing the average more toward 0.6something. Need to look into this.
Unionfind Algorithms
August 25, 2013
Started following CourseraPrinceton’s Algorithms 1.
Being a noncomputer scientist, I started missing these theoretical foundations in some of my recent scientific work, so this course might fill a few gaps.
Too bad they don’t offer any completion certificate (as other Coursera courses do), therefore I won’t be submitting the programming exercises (Java, btw).
Instead, I’ll work on the assignments in Python, to my heart’s content.
We start from the very top: objects belonging to disjoint sets (“connected components”, in graph terms).
Often one wishes to query whether two items belong to the same set and, in case, merge two sets.
If sets are represented as trees, a common tree root node indicates that two given items belong to the same set.
Tree rootfind with recursion
Data structure: is a pointer list, a list of integers which can be traversed recursively to find the root (i.e. root of element is ):
def root(L,ii): "ridx = tree root of element ii" "rd = depth of ii" ridx = ii rd = 0 if L[ii] != ii: ridx, rd = root(L, L[ii]) rd += 1 return ridx, rd
The branch() method outputs the list of nodes connecting ii to its root:
def branch(L,ii): "return branch from ii to root as list" Lout=[ii] if L[ii] != ii: Lout = Lout + branch(L, L[ii]) return Lout
There is an interesting discussion about recursion in Python and its real implications here, the takehome message being simply that one should not implement iterative procedures (‘loops’) as recursion.
QuickUnion
This algorithm needs the items to be arranged in a set of trees (a ‘forest’), so that the set query is simplified to an identity test of the respective tree roots.
Using the code above, this simply reads:
def qu(L, ii1, ii2): "attach subtree of ii2 to root of ii1" ridx1, rd1 = root(L, ii1) ridx2, rd2 = root(L, ii2) L[ridx1] = ridx2 return L
A shortcoming of this approach is that trees tend to get tall and skinny, so searches in them, in the worst case, require operations.
Weighted QuickUnion
The complexity of a search on UnionFind trees can be kept manageable by weighting, i.e. one subtree in WQU is attached to the second’s root if the former’s size is smaller.
A more precise notion of size is in order: e.g. the total number of elements in the subtree or the subtree depth.
If we settle for the latter definition (unionbydepth),
def wqu(L, ii1, ii2): "weighted quick union" "attach subtree of ii2 to subtree of ii1," "if the root distance of former is smaller" ridx1, rd1 = root(L, ii1) ridx2, rd2 = root(L, ii2) if rd1 <= rd2: L[ridx1] = ridx2 else: L[ridx2] = ridx1 return L
This balancing helps to keep the complexity of a search on at (where is the average number of subtree size doublings).
Weighted QuickUnion with Path Compression
An optimization on WQU is given by “path compression”: at union time, all the parents of the node to be attached are set to be the root node of the larger tree.
A (singlepass) WQUPC code reads:
def wqupc2(L, ii1, ii2): "WQU with path compression" B1 = branch(L, ii1) B2 = branch(L, ii2) rd1 = len(B1) rd2 = len(B2) ridx1 = B1[1] ridx2 = B2[1] if rd1 <= rd2: for ii in B1: L[ii] = ridx2 else: for ii in B2: L[ii] = ridx1 return L
While doing what it says on the label, the code above uses two recursive calls to find the branch roots (with the known memory and depth size limitations of recursion), storage of the branches and a loop along the smaller of the two branches.
A smarter implementation is clearly necessary for largescale applications.
If the search tree can be “flattened out” maximally, the complexity of a union search can be further reduced so as to approach (but never reach) the size of the data items.
That is, unionfind operations on objects organized in a flattened tree need less than array accesses, where is the iterated log function (HopcroftUllman, Tarjan).
BTW, the iterated logarithm is defined as the number of times has to be applied in order to obtain , and is an extremely slowly growing function (e.g. ).
Results and conclusions
We list the theoretical worstcase computational burden, along with typical figures for the average branch depth of the trees generated with each algorithm (obtained with sets of n=1000 integers, after 10^5 random union operations):
 Quickunion
Complexity of k searches on n items: O(k n)
Average branch depth range: 124 – 133  Weighted quickunion
Complexity of k searches on n items: O( n + k log2(n) )
Average branch depth range: 5.3 – 8.3  Weighted quickunion with path compression
Complexity of k searches on n items: O( n + k log*2(n) )
Average branch depth: 2.01 (variations at the third decimal)
Path compression clearly minimizes the overhead associated with finding the set label of large collections of items.
Simple code leading to very deep mathematics and enabling hugescale computation .. my appetite, on the other hand, is growing quickly.
Ecosystem crisis in the making?
July 27, 2013
A few days ago, midJuly, a fish dieoff took place in the Venice lagoon [IT].
The authorities [IT] isolated the high oxygen level in water as the culprit, in turn due to an abnormally large seaweed growth (which has been attributed in part to the anomalous climate pattern since the spring: hot and rainy).
It is believed that certain nonindigenous algal varieties, brought to the lagoon on the hulls of cargo ships are thriving in the local ecosystem (yet another game of blametheimmigrant?).
I meant to educate myself on the details for a while now but never found the time.
Seaweed or not, the environmental shock is propagating up the food chain.
Seagulls are already looking miserable, and very few are flying, some noticed.
From a very utilitarian and humancentric point of view, the locals don’t feed on seagull meat, and Venice as a whole has a rather open food system (most of it is imported, as there is precious little agriculture on a couple of the lagoon islands, certainly not enough to support the whole population) but these facts leave me pondering.
However other species might be relying on the ones presently in danger, as predatorprey systems [EN] are in a feedback relationship (a concept which our customersupermarket culture has alienated us from).
I certainly hope we are not witnessing the start of a local environmental collapse.
The Venice lagoon is a unique pool of biodiversity, and its extinction would mean yet another shame on humankind’s record.
Jaron Lanier on the “Localglobal flip”
August 30, 2011
Instead of recalling why this seemingly innocuous chubby Rastafarian is and has been one of the spearheads of contemporary debate about future for .. three decades now, let’s focus on this monologue of his recently recorded by EDGE.
Lanier debates that the widespread usage of networking has reduced the individual to a trade object of corporations and markets, rather than empowered a new middle class that “creates value out of their minds and hearts”.
The promise of the early Internet, to horizontally connect individuals in a heterogeneous global but ultimately personalized trading ground, transformed in a brutal ecosystem where there is no strategy, no planning, only instantaneous profitoriented logic.
In this heavily peaked pyramid, players that are unable to perform realtime, ubiquitous information gathering and decision making are simply left out, as a necessary byproduct of an “early adopter” effect: the first takes all.
(Can this be considered a consequence of finite resources/finite “context size” and/or of smallworld network characteristics? Just my personal note, will think about this)
He also points at possible interpretations of upandcoming technological developments and their use in counteracting this “trend” to restore the production of value to the individual user, which is, he argues, the only way for civilization not to end as either “Matrix or Marx” (avoidable catchy quote).
Enjoy this hourlong thoughtprovoking rollercoaster blah blah, it will crack your mind open like a veritable crowbar!
[blip.tv http://blip.tv/play/hLJxgs77WAA%5D
http://edge.org/conversation/thelocalglobalflip
Open Source Ecology
August 23, 2011
To recognize that human civilization needs to relearn to live IN the ecosystem, and not OFF it.
This is the philosophical manifesto and the life project of Marcin Jakubowski and a growing crew of concerned inventors, builders, makers; to exploit centuries of technological advances and package them as opensource hardware tools for community building, with locality and sustainability as core values.
More concretely, quoting from the Working Assumptions of the Open Source Ecology wiki,
Civilization are shaped by their resource base. The resource base is what gives people power. By controlling others through an economic or social hierarchy, we can control resources, and thus gain power. Resource conflicts occur because people have not yet learned to manage resources without stealing. Society has not transcended the brute struggle for survival. We remain on the bottom steps of Maslow’s pyramid. Transcending resource conflicts by creating abundance, first for hundreds, then for thousands of people, is now possible if knowledge flows openly and advanced technology is applied to produce goods.
and
Education, media, and social engineering programs have subjugated human integrity to passive consumerism, with its related problems (resource conflicts, loss of freedom such as wage slavery). The only way out of this is creating a framework within which humans can prosper: provision of true education, learning of practical skills, stewardship of land, advanced technology for the people, and open access to economically significant knowhow.
See Marcin make his point about transcending artificial scarcity:
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 selfcensorship, as opposed to the easy trigger of too many compulsive selfelected 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,