Algorithms to live by

Túto knižku si so záujmom môžu prečítať aj computer science ľudia, aj tí ostatní. Každá skupina iným spôsobom, ale oba sú dobré. Ľudia, ktorí už kde-tu na nejaký algoritmus natrafili a stretli sa s nejakými jeho hraničnými prípadmi, sa nedozvedia z informatiky veľa nového, ale dostanú zaujímavé súvislosti a príklady (áno, aj zo skutočného života) a počiatočné podmienky na rozmýšľanie novým smerom. Tá druhá skupina ľudí dostane prístupným spôsobom vysvetlené aj celkom netriviálne veci, čo samo o sebe vôbec nie je málo a navyše môže tiež oceniť prepojenia na rôzne životné situácie a rozhodnutia, ktoré v nich robíme. Niektoré príklady sú uletené, niektoré prehnané, ale z veľa z nich sa dá niečo si zobrať.


But for the computer scientists who wrestle with such problems, this verdict isn’t the end of the story. Instead, it’s more like a call to arms. Having determined a problem to be intractable, you can’t just throw up your hands. As scheduling expert Jan Karel Lenstra told us, “When the problem is hard, it doesn’t mean that you can forget about it, it means that it’s just in a different status. It a serious enemy, but you still have to fight it.” And this is where the field figured out something invaluable, something we can all learn from: how to best approach problems whose optimal answers are out of reach. How to relax.

If you want to be a good intuitive Bayesian, if you want to naturally make good predictions, without having to think about what kind of prediction rule is appropriate – you need to protect your priors. Counterintuitively, that might mean turning off the news.

Communication is one of those delightful things that work only in practice; in theory it’s impossible.

Named for Nobel Prize-winning economist William Vickrey, the Vickrey auction, just like the first-price auction, is a “sealed bid” auction process. That is, every participant simply writes down a single number in secret, and the highest bidder wins. However, in a Vickrey auction, the winner ends up paying not the amount of their own bid, but that of the second-place bidder. That is to say, if you bid $25 and I bid $10, you win the item at my price: you only have to pay $10.

A doctor told me about her approach to keeping things. “My kids think I’m whacky, but I put things where I think I’ll need them again later, even if it doesn’t make much sense.” As an example of her system, she told me that she keeps extra vacuum cleaner bags behind the couch in the living room. Behind the couch in the living room? Does that make any sense? It turns out that when the vacuum cleaner is used, it is usually used for the carpet in the living room… When a vacuum cleaner bag gets full and a new one is needed, it’s usually in the living room. And that’s just where the vacuum cleaner bags are.

Perhaps the patron saint of the minimal-context-switching lifestyle is the legendary programmer Donald Knuth. “I do one thing at a time,” he says. “This is what computer scientists call batch processing—the alternative is swapping in and out. I don’t swap in and out.” Knuth isn’t kidding. On January 1, 2014, he embarked on “The TeX Tuneup of 2014,” in which he fixed all of the bugs that had been reported in his TeX typesetting software over the previous six years. His report ends with the cheery sign-off “Stay tuned for The TeX Tuneup of 2021!” Likewise, Knuth has not had an email address since 1990. “Email is a wonderful thing for people whose role in life is to be on top of things. But not for me; my role is to be on the bottom of things. What I do takes long hours of studying and uninterruptible concentration.” He reviews all his postal mail every three months, and all his faxes every six.

Víkendové surfovanie

in praise of mediocrity

But there’s a deeper reason, I’ve come to think, that so many people don’t have hobbies: We’re afraid of being bad at them. Or rather, we are intimidated by the expectation — itself a hallmark of our intensely public, performative age — that we must actually be skilled at what we do in our free time. Our “hobbies,” if that’s even the word for them anymore, have become too serious, too demanding, too much an occasion to become anxious about whether you are really the person you claim to be.

If you’re a jogger, it is no longer enough to cruise around the block; you’re training for the next marathon. If you’re a painter, you are no longer passing a pleasant afternoon, just you, your watercolors and your water lilies; you are trying to land a gallery show or at least garner a respectable social media following. When your identity is linked to your hobby — you’re a yogi, a surfer, a rock climber — you’d better be good at it, or else who are you?

pendulum and marble

platiť sa dá aj osobnými údajmi

Zajtra ráno prednášam informatikom o konečných stavových automatoch a Turingových strojich. Pri tej príležitosti

It’s rare for a CS major to graduate without getting a healthy dose of NP-completeness and Turing machines, two beautiful areas of theory that would be enjoyable if they didn’t end up creating bad instincts. One biologist asked me to solve a problem in DNA sequence matching and I came back to him with the claim that it was NP-complete, a class of problems that can take a very long time to solve. He didn’t care. He needed to solve it anyway. And it turns out that most NP-complete problems are pretty easy to solve most of the time. There are just a few pathological instances that gum up our algorithms. But theoreticians are obsessed with the thin set that confound the simple algorithms, despite being rarely observed in everyday life.

The same problem happens with Turing machines. Dutiful CS students learn nihilistic results like Rice’s Theorem, which shows that we really can’t analyze computer algorithms at all. But Turing machines are a pretty bad model for how our regular machines operate and it’s often very easy to create software that does smart things with our code. Any CS major who doesn’t take these theoretical results with a healthy dose of salt risks giving up when a perfectly usable answer is close at hand.

Visualizing street orientations on an interactive map … tu sú niektoré svetové mestá a tu je Žilina:

improve in foreign languages by reading books in parallel