My favorite artistic illustration is probably Jorge Stolfi's drawing inspired by the self-adjusting splay tree data structure of Sleator and Tarjan:
https://www.link.cs.cmu.edu/splay/tree5.jpg
Readit NewsDeleted Comment
lkozma commented on Ask HN: What's your favorite illustration in computer science? · Posted by u/gnull
lkozma commented on Ask HN: What's your favorite illustration in computer science? · Posted by u/gnull
There's an important distinction that your explanation glosses over, which is that MergeSort is an out-of-place sort while QuickSort is in-place. As a practical matter, this distinction is important and it makes the two algorithms not quite duals. Your explanation of why we can assume that QuickSort pivots are medians makes sense, but it also glosses over one of the deep insights about why QuickSort works at all, which is that with unsorted data, the choice of pivot will rarely be bad (it will be "near the middle on average.")
Yes, this efficiency-aspect is not captured in the illustration -- while splitting perfectly _by index_ comes for free, splitting perfectly _by value_ needs nontrivial work (median-finding).
lkozma commented on Ask HN: What's your favorite illustration in computer science? · Posted by u/gnull
May I add one that I made?
Illustration of QuickSort and MergeSort as two sides of the same coin: http://lkozma.net/images/sort/duality.pdf
I find this somehow both obvious and counter-intuitive, and usually the two algorithms are not presented in this way, as duals of each other.
I wrote up this view in more detail, but the figure above should be self-explanatory: http://lkozma.net/blog/a-dual-view-of-sorting-algorithms/
Deleted Comment
Deleted Comment
When I was a kid, you could buy 4 or so different soft drinks, a few juices and some flavoured milks. Now, the drink fridges take up a whole wall in the store, and there are multiple waters, flavoured waters, sparkling waters, non-sugar soft drinks, the usual big brand soft drinks but with many varieties, iced teas, energy drinks of all sorts, many juice permutations, multiple coffee drinks, protein shakes, kombucha, specialised kiddy drinks… the explosion in options is quite striking. I assume this is because selling drinks is a good business, essentially reselling people their tap water for a huge margin. I also think that the gargantuan marketing expenditure of Coke and friends has deeply implanted the idea of drinking from bottles into a whole generation, and other drink makers benefit from this advertising ‘penumbra’.
Socrates supposedly loved going to the market. When his students asked him about this, Socrates replied, "I love to go and see all the things I am happy without." :)
Deleted Comment
Polyominoes have been obsessing me. Not tiling but counting them. No formula has been yet found. Their free numbers (i.e up to rotations and flipping) go
1, 1, 2, 5, 12, 35, 108, 369, 1285, ...
■
■
■
■
■
■
■ ■
■
■ ■
■
■
■ ■
■
■ ■
■ ■
I've been (nowhere as a mathematician) exploring this problem for years, generating them and trying in vain to find patterns in their properties.
I'd love readers with a high view in combinatorics telling what they think of this problem. Do you think a formula will one day be found or rather that there can't be a closed one for some necessary reason ?
This is a very nice and deep question. Are you aware of the published research on the problem?
The growth rate is indeed around 4 and now known to be strictly above 4: https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf
If I remember correctly, there was a non-rigorous argument for a concrete conjectured value not far above 4.
I hear this a lot and I'm happy for the author, but the "divinity" of math is not something that has ever resonated with me, not even when I was younger.
It's a tool. It's by far the most powerful tool man has ever made, because it's a tool for your mind as opposed to a tool for your hands, but it still is a tool.
"Seeing an astronomer using a telescope to observe a galaxy, no-one will confuse the telescope with the galaxy. Mathematics differs from science in that there is no clear distinction between the tools and the objects of study." -- D.Aldous