Re: How powerful is mp?

[Marco Kuhlmann <marco.kuhlmann@gmx.net>]

    Hi Taco.

Thanks for the qobitree recommendation for a stack-based
tree-drawing algorithm. qobitree assumes that the trees have a
rectangular envelope, yuk...

Taco Hoekwater wrote (2001-11-08 (09:33)):

> Kennedy's implementation uses quadratic time. With all respect
> for the author himself, I think his article is not very
> exciting. 

So what sub-quadratic algorithms are there?

> He does indicate that the implementation can be changed to use
> linear time, but doesn't actually show the code that would
> result from that.  That would have been a lot more interesting
> that a couple of recursive functional programming procedures
> that are all virtually trivial.

One could also say: they show how straightforwardly the problem
can be formulated in a functional programming language. :-)
However, you are right that he should have shown the linear
version as well. I actually wonder if there is one; I spent
some time but couldn't figure it out. Gibbons has shown a
linear bound for binary trees, but for n-ary trees...

    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net