Algorithms from the “Book”(cstheory.stackexchange.com)
cstheory.stackexchange.com
Algorithms from the “Book”
http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?
13 comments
Well, I downvoted. This is psuedo-philosophical nonsense that seems to be saying something profound, but isn't really. Nor does it add to a discussion on interesting algorithms. We could just as easily say that nature is a poor approximation of math, like shadows on a cave wall are poor approximations of the real object.
In what way is a "discussion on interesting algorithms" not already pseudo-philosophical?
But OK, I'll do it your way:
An interesting class of algorithms is finite-difference approximations [1]. Even more interesting are algorithms for designing such approximations [2]. A key insight to making these algorithms work is that Taylor series approximations can be used to study the truncation errors of discrete approximations to continuous phenomena. However these techniques, by themselves, mainly interest me in the context of the physical problems they are meant to address. Since those problems come from the physical world, I would argue that the algorithms themselves don't satisfy the formal criteria set forth in the original question, of what algorithms god would write down in a book.
[1] See LeVeque, "Finite Difference Methods for Ordinary and Partial Differential Equations".
[2] See Hamming, "Numerical Methods for Scientists and Engineers".
But OK, I'll do it your way:
An interesting class of algorithms is finite-difference approximations [1]. Even more interesting are algorithms for designing such approximations [2]. A key insight to making these algorithms work is that Taylor series approximations can be used to study the truncation errors of discrete approximations to continuous phenomena. However these techniques, by themselves, mainly interest me in the context of the physical problems they are meant to address. Since those problems come from the physical world, I would argue that the algorithms themselves don't satisfy the formal criteria set forth in the original question, of what algorithms god would write down in a book.
[1] See LeVeque, "Finite Difference Methods for Ordinary and Partial Differential Equations".
[2] See Hamming, "Numerical Methods for Scientists and Engineers".
You are right. By purposefully misinterpreting "god" to be literal, you have won the discussion of what he would write in a book. Your answer is the best. Congratulations.
That's not at all what "The Book" means, though!
The idea is that a proof from "The Book" feels perfect in the same way that, say, listening to Bach does. Less natural, more transcendental.
The idea is that a proof from "The Book" feels perfect in the same way that, say, listening to Bach does. Less natural, more transcendental.
Tl;dr algorithms are representations of processes occurring in reality.
That's really all I could understand from this. I would love to hear what would "algorithms being woven into the fabric of the physical world" even mean?
That's really all I could understand from this. I would love to hear what would "algorithms being woven into the fabric of the physical world" even mean?
By "woven into the fabric" I mean that the physical world executes what we think of as algorithms, as part of its natural existence. We write an equation that represents viscosity, but nature just executes viscosity because of the way the atoms interact. Or rather, viscosity emerges because of the way things interact. There is no equation, there is no computational organization, there is no unit testing, there's just doing-- at massive scale.
By the way, I would say not all algorithms occur in reality, and when they do, nature isn't necessarily very good at them. For example, sort and binary search just don't seem that high up on the list of things the physical world cares about. The natural sorting process by which dirt in a container separates out into various gradations of size, corresponds to bubble sort-- not an especially efficient algorithm.
By the way, I would say not all algorithms occur in reality, and when they do, nature isn't necessarily very good at them. For example, sort and binary search just don't seem that high up on the list of things the physical world cares about. The natural sorting process by which dirt in a container separates out into various gradations of size, corresponds to bubble sort-- not an especially efficient algorithm.
"All models are wrong, but some [models] are useful." - George E. P. Box
For all we know, nature is a very slow, serialized computation.
http://xkcd.com/505/
http://xkcd.com/505/
See also "Proofs from the Book" by Martin Aigner & Günter M. Ziegler, illustrated by Karl H. Hofmann.
(Edit: oh wait, the book is linked at the beginning of the SO thread. Never mind :) )
http://www.amazon.co.uk/Proofs-THE-BOOK-Martin-Aigner/dp/3642008550
(Edit: oh wait, the book is linked at the beginning of the SO thread. Never mind :) )
Because there's no Kindle version of "Proofs from the Book", I didn't order it. But I did see in the recommended list a book called, "How to Solve It"....which is apparently a popular general purpose problem solving book that, according to a reviewer, was given to Microsoft's new programmers. Less than $10 on Kindle so hopefully this will scratch the proof-solving itch for me:
http://www.amazon.com/How-Solve-It-Mathematical-Princeton/dp...
http://www.amazon.com/How-Solve-It-Mathematical-Princeton/dp...
There was a Kindle edition for the 3rd edition of the book, but it was justifiably withdrawn. Here was my review on Amazon to warn people against buying it:
=================
The Kindle edition is completely worthless, because it is missing many symbols. It appears to have been done using OCR, and it was confused by mathematical symbols. For example, there are some places where I THINK it was supposed to be the greek letter phi, but it comes out as a left parenthesis and a right parenthesis. At least with that you can figure out what it was supposed to be. There is much worse--places where symbols are completely gone. E.g., there is a place where you just get a capital sigma with a subscript giving a summation limit, a blank space, a less than sign, and another blank space. So, the proof is saying the some of something is less than something else.
This is a shame, because the book itself, from what I can see, is EXCELLENT.
=================
This illustrates a major annoyance with Amazon's review system. They combine reviews for all formats of a book. This is bad both from the review side and the potential purchaser side.
From the review side, how many stars should I have given the book? The non-Kindle versions are excellent. 5 stars. The Kindle edition, as I said, was completely worthless. 1 star. So do I give 5 stars or 1 star? 3 stars?
From the purchaser side, the combined reviews are annoying because I want to see the reviews specifically for the format I'm considering. For "Proofs from the Book" this is not too much of a problem because there are only 17 reviews. I can just read them all. For books with hundreds of reviews, it is a problem.
As far as math books on Kindle go, PftB is the worst I've tried, but I've not actually found any math book that was acceptable to me. The others I've seen have had all the symbols there, but it was done by having the math handled as embedded images, which did not resize if I changed the font size, and were smaller than the math in the paper book.
=================
The Kindle edition is completely worthless, because it is missing many symbols. It appears to have been done using OCR, and it was confused by mathematical symbols. For example, there are some places where I THINK it was supposed to be the greek letter phi, but it comes out as a left parenthesis and a right parenthesis. At least with that you can figure out what it was supposed to be. There is much worse--places where symbols are completely gone. E.g., there is a place where you just get a capital sigma with a subscript giving a summation limit, a blank space, a less than sign, and another blank space. So, the proof is saying the some of something is less than something else.
This is a shame, because the book itself, from what I can see, is EXCELLENT.
=================
This illustrates a major annoyance with Amazon's review system. They combine reviews for all formats of a book. This is bad both from the review side and the potential purchaser side.
From the review side, how many stars should I have given the book? The non-Kindle versions are excellent. 5 stars. The Kindle edition, as I said, was completely worthless. 1 star. So do I give 5 stars or 1 star? 3 stars?
From the purchaser side, the combined reviews are annoying because I want to see the reviews specifically for the format I'm considering. For "Proofs from the Book" this is not too much of a problem because there are only 17 reviews. I can just read them all. For books with hundreds of reviews, it is a problem.
As far as math books on Kindle go, PftB is the worst I've tried, but I've not actually found any math book that was acceptable to me. The others I've seen have had all the symbols there, but it was done by having the math handled as embedded images, which did not resize if I changed the font size, and were smaller than the math in the paper book.
Making a mathematical book in mobi/epub is a difficult problem but I'm surprised the publishers weren't aware of the difficulties.
Simple statements can be expressed in pure Unicode (though the Kindle fonts have incomplete Unicode support for the relevant blocks). Anything more than that has to be an image, which is the bane of digital publishing, since it won't scale with the base font size. epub 3 might be able to cope with it but apart from iBooks I don't know anyone else using it.
Simple statements can be expressed in pure Unicode (though the Kindle fonts have incomplete Unicode support for the relevant blocks). Anything more than that has to be an image, which is the bane of digital publishing, since it won't scale with the base font size. epub 3 might be able to cope with it but apart from iBooks I don't know anyone else using it.
For those images at 600dpi seem to be the way to go. I'm pretty sure you'll be able to get by with 2-bit black&white images at that resolution.
I ordered the hardcover Proofs a few weeks ago after seeing the Calkin-Wilf tree [1] [2]. I cannot suggest it on the Kindle because you're going to want to write in it—there are even large margins to encourage this kind of behavior.
[1] http://hackage.haskell.org/packages/archive/prelude-safeenum... [2] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals...
It's one of the best books I've ever bought measured in raw joy and satisfaction per page. Like all proofs, reading is a very involved process, but these are genuinely stunning ones.
[1] http://hackage.haskell.org/packages/archive/prelude-safeenum... [2] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals...
It's one of the best books I've ever bought measured in raw joy and satisfaction per page. Like all proofs, reading is a very involved process, but these are genuinely stunning ones.
If I recall correctly, this book also comes very highly recommended from Rich Hickey, the author of Clojure.
This is part of a series. I haven't read Solve It but there is another one that I worked through several years ago before returning to school, How to Prove It, that really cleared up how to do proofs for me. It is all based around set theory and some of the later proofs are quite deep:
http://www.amazon.com/gp/aw/d/0521675995/
http://www.amazon.com/gp/aw/d/0521675995/
Not part of a series. "How to solve it" was written long before "How to prove it", and the latter was presumably named in homage to Polya's book. (Though I don't think it has much in common.)
There's another recent mathsy book called "How to solve it: modern heuristics" which is actually about optimization algorithms and has basically nothing to do with Polya's book.
There's another recent mathsy book called "How to solve it: modern heuristics" which is actually about optimization algorithms and has basically nothing to do with Polya's book.
HashLife is one of the algorithms from the book. I wrote a simple implementation in CoffeeScript and tried answering the following question:
"If you set up a Glider Gun when the Earth was first formed 4.5 billion years ago, and ran one generation per second, in the 143.4 quadrillion seconds that have elapsed since then, how many cells would be alive?"
In less than three seconds, my 2010 iMac had the answer: the pattern would grow to 23,900,000,000,000,036 live cells.
https://en.wikipedia.org/wiki/Hashlife
"If you set up a Glider Gun when the Earth was first formed 4.5 billion years ago, and ran one generation per second, in the 143.4 quadrillion seconds that have elapsed since then, how many cells would be alive?"
In less than three seconds, my 2010 iMac had the answer: the pattern would grow to 23,900,000,000,000,036 live cells.
https://en.wikipedia.org/wiki/Hashlife
Hashlife's pretty sweet although that particular answer you can get in time too short to measure by just typing some multiplications and divisions into a calculator. A glider contains 5 cells, a glider gun 36 and after the first glider at generation 15, the glider gun churns out a new glider every 30 generations, like clockwork.
True, although this reminds me of an old Von Neumann joke (it was probably a Newton joke once):
A colleague walks up to Von Neumann at a party. "Hey!" he challenges. "Two locomotives are speeding towards each other on a track. They begin ten miles apart and are both travelling at 30mph."
"A fly on the hood of one locomotive flies to the other locomotive at 60mph, then returns to the first, and keeps going back and forth between them until the two crash, killing the fly."
"How far has the fly travelled?"
Von Neumann considers, then gives the correct answer. "It's true," his colleague says, "you can instantly see the insight to any problem. You knew that you could merely sort out how long it takes and then work out the distance from the fly's speed."
Von Neumann frowns. "It seemed simpler to sum the series in hy head, and it's a more general solution."
A colleague walks up to Von Neumann at a party. "Hey!" he challenges. "Two locomotives are speeding towards each other on a track. They begin ten miles apart and are both travelling at 30mph."
"A fly on the hood of one locomotive flies to the other locomotive at 60mph, then returns to the first, and keeps going back and forth between them until the two crash, killing the fly."
"How far has the fly travelled?"
Von Neumann considers, then gives the correct answer. "It's true," his colleague says, "you can instantly see the insight to any problem. You knew that you could merely sort out how long it takes and then work out the distance from the fly's speed."
Von Neumann frowns. "It seemed simpler to sum the series in hy head, and it's a more general solution."
Definitely a Von Neumann joke, the only unusual thing about it is that the terms themselves weren't infinite series.
Did you end up releasing your Coffeescript implementation? There's stuff like Golly but not a great deal in the way of readable higher-level language implementations out there.
Did you end up releasing your Coffeescript implementation? There's stuff like Golly but not a great deal in the way of readable higher-level language implementations out there.
I've heard it attributed to Feynman, though I don't remember where.
For every different tree type i see ,
A searching tree i make it be,
The fruit u see ; are like a key,
i see u on the leaf nodes be.
An Algo by the Almighty.
(tl;dr ) Whenever i see a real tree it looks to me like a specialized tree data structure implemented by the Almighty.
Also i tried to add little programming puns in my pseudo enigma styled poem thing.
(tl;dr ) Whenever i see a real tree it looks to me like a specialized tree data structure implemented by the Almighty.
Also i tried to add little programming puns in my pseudo enigma styled poem thing.
I don't know if it is particularly elegant, but I have a soft spot for Bresenham's line algorithm - it's not so much about lines as it is an algorithm to repeatedly add fractions to an accumulator using only addition and subtraction and without rounding errors (altough intermediate results are rounded to their nearest integer value).
Bresenham's line algorithm generalises trivially to drawing trapezoids, too. There's also Bresenham's elliptic arc drawing algorithm that's similarly beautiful.
Immediately upon seeing this I found myself jumping to click through - the idea is somewhat flawed (subjectivity (which people call 'beauty in the eye of the beholder' :P)) but an enjoyable one nonetheless.
To anyone who hasn't read it, I would heartily recommend 'Proofs from the Book' but moreso than that, to those who regularly come in contact with (semi-)formal methods (be they mathematical or logical) I would heartily recommend looking out for proofs that catch your eye like that and debating their worthiness for 'The Book'- it's a fun exercise! :)
To anyone who hasn't read it, I would heartily recommend 'Proofs from the Book' but moreso than that, to those who regularly come in contact with (semi-)formal methods (be they mathematical or logical) I would heartily recommend looking out for proofs that catch your eye like that and debating their worthiness for 'The Book'- it's a fun exercise! :)
Richard Bird took "Proofs from the Book" as an inspiration for his "Pearls of Functional Algorithm Design". I read a bit in it recently and there are really quite a few nice dderivations of functional programs, where the mathematical and the implementation part go hand in hand.
I'm a fan of Fortune's Algorithm: http://en.wikipedia.org/wiki/Fortune%27s_algorithm Voronoi diagrams in general have lots of nifty applications... e.g. game worlds http://www-cs-students.stanford.edu/~amitp/game-programming/...
If there are intelligent aliens out there and they have to search a sorted sequence then they certainly have developed binary search. So, I nominate 'binary search'.
I would definitely include merge sort on this list, since it is simultaneously simple and efficient. Also, if we are willing to include data structures in this, I would throw in a vote for skew binary random access lists:
http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture0...
http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture0...
I have a soft spot for Radix Sort. Not for any good reason but the fact that it is counter-intuitive, and that, more than anything, expresses how different perspectives can be used to gain insight into interesting problems.
https://en.wikipedia.org/wiki/Radix_sort
https://en.wikipedia.org/wiki/Radix_sort
"The Book" is all around us. The algorithms that nature cares about are woven into the fabric of the physical world. Our algorithms are just poor approximations, intended to make simulation tractable on discrete computers.
For example, this site occasionally carries posts about making water look realistic in games. Those posts usually acknowledge that the graphics approach they describe is cheating compared to actually solving the Navier-Stokes equations. But the NS equations are just a mathematical expression of reality. We then cook that mathematical expression down even more, in order to arrive at a collection of algorithms (finite-difference approximations, domain partitioning, numerical solvers) that attempt to embody the math.
Yet problems that today we would consider impossibly hard to solve computationally-- for example, fully resolving the flow of water around a sailboat, not to mention the wind in its sails, and the stresses in the mast-- nature solves billions upon billions upon billions of times a second.