lkozma

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

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).

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/

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." :)

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.

"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

You are right in general, but when the quote is from someone on whose research the result builds in an important way (as it is the case here), I would say it is fair.

Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).

For an example, consider 2^sqrt(log(n)).

This is a bit similar to something being faster than polynomial, but slower than exponential.

Who is pushing/lobbying for that type of legislation? Isn't it a case of regulation helping the incumbents?

For those coming from a CS background a possible (crude) intuition sometimes given is that

frequentist :: Bayesian ~ worst-case analysis :: average-case analysis

There are a good reasons why we don't usually do average-case analysis of algorithms, chief among them that we have no idea how inputs are distributed (another reason is computational difficulty). Worst-case bounds are pessimistic, but they hold.

Honest question: who does it harm? These aspects that you mention may not be to your (or to my) taste, but if they are relatively harmless and the other stuff is overwhelmingly good, why not let it go?

was posted here sometime ago:

The door refused to open. It said, "Five cents, please." He searched his pockets. No more coins; nothing. "I'll pay you tomorrow," he told the door. Again he tried the knob. Again it remained locked tight. "What I pay you," he informed it, "is in the nature of a gratuity; I don't have to pay you." "I think otherwise," the door said. "Look in the purchase contract you signed when you bought this conapt." In his desk drawer he found the contract; since signing it he had found it necessary to refer to the document many times. Sure enough; payment to his door for opening and shutting constituted a mandatory fee. Not a tip. "You discover I'm right," the door said. It sounded smug. From the drawer beside the sink Joe Chip got a stainless steel knife; with it he began systematically to unscrew the bolt assembly of his apt's money-gulping door. "I'll sue you," the door said as the first screw fell out. Joe Chip said, "I've never been sued by a door. But I guess I can live through it."

(Philip K. Dick: Ubik)

> The Soviets royally sucked in the computation department

To add more nuance, there is an essay [1] telling the history of early maximum flow algorithms and includes this small anecdote:

[An] American asked: ".. how were you able to perform such an enormous amount of computing with your weak computers" to which the Russian responded: "we used better algorithms".

There is some truth to that, besides maximum flow, similar stories can be told about linear programming, data structures (e.g. AVL-trees), numerical computing, etc. The hardware may have been sloppy, but the algorithms-research was top notch.

[1] http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf

Tolstoy along similar lines: https://en.wikipedia.org/wiki/How_Much_Land_Does_a_Man_Need%...

> However, you're being "too smart for your own good" if you go down this route. A perfectly unbiased input would still have 50% of its inputs rejected, and already you've dropped the speed of the RNG by 50%.

To improve this situation you can use an additional trick: keep track of the sequence of thrown-away pairs, and look at them again in consecutive pairs, and generate some more random bits:

* 00 00 -- throw away

* 11 11 -- throw away

* 00 11 -- output 1

* 11 00 -- output 0

and so on..

see the paper "Iterating Von Neumann's Procedure for Extracting Random Bits" for details.

That's true, but "high school algebra" in some countries also includes some group/ring theory basics (or it used to).

One small thing in the latest redesign: if you have two tabs, one active, one not, the visual cues suggest exactly the opposite. The active one seems like a clickable button, the inactive one seems pushed down and not clickable.

After misclicking hundreds of times, I still couldn't train myself to go against my perception and follow the designer's "bold vision", using it feels like writing with my left hand or steering a bicycle with a crooked wheel.

I recognize the symptoms you describe, but I find the picture you painted a bit too pessimistic, given that in the field that I'm familiar with (theoretical CS), groups in Poland have been among the strongest and most visible in Europe in the past 10 years.

This seems like a very accurate description, especially the observation about temporal continuity, which we take for granted, but on occasions it can feel like a fragile illusion.

Relatedly, there was an unintentionally funny translation of Gmail in Hungarian, where it was supposed to say "You have no conversations in Trash", or something like that. The translation was technically correct, but it sounded very much like "No more talking in the trashcan!", which was hard to read without imagining someone shouting at a trashcan with a person inside it.

By that logic, take all the paint away from Van Gogh and give it all to Jeff Koons.

There could be more courses that teach the necessary programming techniques but also case studies of problems that have been solved this way. For example, the course "Experimental Mathematics" given by Doron Zeilberger.

A long time ago I had taught a class on data visualization, and used this photo as example of creative use of pie charts:

https://www.answerminer.com/static/489716080133492e99fdcb9c8...

Here was another list: http://avoinelama.fi/hingo/kirjoituksia/misleadingvisualizat...

Yes, "competible" would be good for the opposite situation.

The step from tracking zero things to tracking one thing may be larger then the step from tracking one thing to tracking (almost) everything.

They probably referred to this:

https://en.wikipedia.org/wiki/Generative_topographic_map

That's a great observation. There was a _very long_ but funny and insightful article expanding on this issue, calling such interfaces "hubristic": http://unqualified-reservations.blogspot.de/2009/07/wolfram-...

Yes, I think von Neumann made this claim somewhere already that AI is a moving target, because once some task is automated it doesn't seem intelligent anymore.

This is a valid criticism from a practitioner point of view. From someone doing research in algorithms and data structures or someone just curious about it at an intellectual level, there is a different criticism:

All this focus on algorithms for the sake of interview-preparation gives the false impression that the field is a closed body of work. In reality it is an active and lively field of research with many (even most) basic questions not yet understood.

Someone could go through these 500 questions and for (almost) all of them formulate variants/extensions that would be open research questions. So instead of memorizing them, ask for each: Is this the best possible solution? Can I prove it? What if I restrict what the algorithm can do? What if I give the algorithm extra powers? What if the data comes online? What if the input is noisy? What if I want to optimize space usage instead of time? Is there a trade-off between the two? Etc. etc.

And related to the parent question: does the problem model a real practical problem? Why not? Can the model be changed to be more realistic?

All that being said, at a first look, the list seems like a quite nice collection of techniques.

Isn't this the broken window fallacy?