Timeline for Algorithms from the Book
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 16, 2015 at 17:08 | comment | added | Will Sawin | The claim that "this only works because the numbers are just right to fit in the master theorem" is not really true. If you replace the number $5$ with a larger number $n$, it is easy to see that the two numbers that have to sum to less than $1$ converge to $3/4$ and $0$, so all sufficiently large $n$ work. $5$ is just the first number that works, it's not the only one. | |
| Nov 23, 2013 at 15:37 | comment | added | Chad Brewbaker | Ruby implementation, gist.github.com/chadbrewbaker/7202412 Is there a version of the algorithm that uses (constant,log) space, or do you have to use linear scratch space to hold the medians? | |
| Jun 16, 2013 at 15:00 | history | edited | Chris Pacejo | CC BY-SA 3.0 |
"recurse" isn't a word ("recur" is)
|
| Mar 30, 2012 at 22:36 | comment | added | Sasho Nikolov | BTW once you parametrize the size of the groups, the constants are not so magical. they are of course optimized to give the right thing in the Master theorem | |
| Mar 30, 2012 at 22:34 | comment | added | Sasho Nikolov | This is one of my favorite algorithms. I like an intuition for it that I learnt from Chazelle's discrepancy book: the set of medians of groups of $1/\epsilon$ elements is like an $\epsilon$-net for intervals in the ordered list of the input numbers. So the algorithm follows a general paradigm: compute an $\epsilon$-net fast, solve the problem on the net, recurse on some part of the input to refine the solution, until you have the exact solution. it's very useful technique | |
| Sep 12, 2010 at 4:02 | history | edited | Jeffε | CC BY-SA 2.5 |
deleted 89 characters in body
|
| Aug 18, 2010 at 16:04 | history | edited | Jukka Suomela | CC BY-SA 2.5 |
highlight, link
|
| Aug 17, 2010 at 20:54 | history | answered | Derrick Stolee | CC BY-SA 2.5 |