3 ms·

This was the focus of my advanced algorithms course at Georgia Tech in my senior year. We had basically a full semester on random algorithms, and I remember wal

This was the focus of my advanced algorithms course at Georgia Tech in my senior year. We had basically a full semester on random algorithms, and I remember walking out each day feeling like the fancy algorithms I'd memorized the previous year were a bit less glamorous. The number of algorithms that removed multiple complicated stateful steps with 'and we randomly select an element from the array' was mindblowing. As I work on more and more distributed systems I keep seeing opportunities for simplifications with randomness (with obvious drawbacks on occasion).

eru 6y ago
Yes! Randomised algorithms are my favourite. You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort. In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run. Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential. In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees. (k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)
ourlordcaffeine 6y ago
Do you know any good books or resources to read up more on random algorithms?
- eru 6y ago
  See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-nutsbolts.pdf https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n... And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms. https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting. You can find a lot of good material just via Google, actually. If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Discrepancy Method - Randomness and Complexity' available at https://www.cs.princeton.edu/~chazelle/pubs/book.pdf https://www.cs.princeton.edu/~chazelle/pubs/book.pdf But it's not for the faint of heart.
  - maxov 6y ago
    I'm surprised and delighted to see someone recommend The Discrepancy Method by Chazelle. I love this book, but even beyond it requiring a lot of mathematical prerequisites, I'm not sure of the use to most software engineers. I think only the chapters on sampling, geometric algorithms, minimum spanning trees, and maybe linear programming would be useful references on algorithm design for most software engineers. I second the recommendation of Probability and Computing by Mitzenmacher and Upfal. In addition to being much more mathematically self-contained, there is more focus on models and techniques that I imagine software engineers might actually use, e.g. hashing, load balancing. In addition, Randomized Algorithms by Motwani and Raghavan is a fantastic book, and should be doable after completing Mitzenmacher and Upfal. It goes into further depth on techinques for designing randomized algorithms. A bit orthogonal but still related to the idea of "what should a software engineer read for interesting algorithm ideas", I really like Approximation Algorithms by Shmoys and Williamson. There is some intersection with randomized algorithms there too.
    - eru 6y ago
      Chazelle also came up with the ingenious soft heaps. I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. I have to admit, I only managed to work through some of the chapters in the books I recommended. And for example, the main reason I know of Chazelle's book it's because it is available for free online and stumbled across it a while ago. Btw, you seem knowledgeable. I have an algorithmic puzzle that has plagued me for some years now: Starting with an empty heap, and a sequence of inserts and min-pops, can you compute what elements will be left in the heap at the end in linear (expected) time? Obviously, you can't just run the instructions, that would take O(n log n) time. I have an algorithm to verify a proposed solution in linear time. But I don't have anything solid for finding one in linear time. I have a hunch that soft-heaps might be useful. And there's probably an even simpler probabilistic approach. Ideally, I'd like the solution in the comparison model, but if you have something that works on numbers only, that's also fine.
      - 6y ago
- FiberBundle 6y ago
  Probability and Computing by mitzenmacher is a very good book

eru 6y ago

Yes! Randomised algorithms are my favourite. You can sometimes put all the randomness in one part of the algorithm, even. Like shuffling before a naive quicksort. In practice that's often even easier to understand (and debug!) than algorithms that keep making random choices as they run. Shuffling and sorting are two humble but powerful building blocks of many algorithms. Both distributed and sequential. In the example of what I did at Goldman, the core of the problem was essentially a souped up multi-dimensional bin packing problem. The big insight was that the typical distribution of our input data, random assignments had a high enough chance of being good, so we didn't need to keep track of everything in k-d-trees. (k-d-trees are also awesome. And I even implemented randomized k-d-treaps at first, before I hit on an even simpler solution.)

ourlordcaffeine 6y ago

Do you know any good books or resources to read up more on random algorithms?

eru 6y ago
See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-nutsbolts.pdf https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n... And https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor... describes one of my favourite algorithms. https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf https://www.cs.au.dk/~gudmund/Documents/randompearlnotes.pdf is also interesting. You can find a lot of good material just via Google, actually. If you read the likes of The Art of Computer Programming for breakfast, you might like 'The Discrepancy Method - Randomness and Complexity' available at https://www.cs.princeton.edu/~chazelle/pubs/book.pdf https://www.cs.princeton.edu/~chazelle/pubs/book.pdf But it's not for the faint of heart.
- maxov 6y ago
  I'm surprised and delighted to see someone recommend The Discrepancy Method by Chazelle. I love this book, but even beyond it requiring a lot of mathematical prerequisites, I'm not sure of the use to most software engineers. I think only the chapters on sampling, geometric algorithms, minimum spanning trees, and maybe linear programming would be useful references on algorithm design for most software engineers. I second the recommendation of Probability and Computing by Mitzenmacher and Upfal. In addition to being much more mathematically self-contained, there is more focus on models and techniques that I imagine software engineers might actually use, e.g. hashing, load balancing. In addition, Randomized Algorithms by Motwani and Raghavan is a fantastic book, and should be doable after completing Mitzenmacher and Upfal. It goes into further depth on techinques for designing randomized algorithms. A bit orthogonal but still related to the idea of "what should a software engineer read for interesting algorithm ideas", I really like Approximation Algorithms by Shmoys and Williamson. There is some intersection with randomized algorithms there too.
  - eru 6y ago
    Chazelle also came up with the ingenious soft heaps. I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. I have to admit, I only managed to work through some of the chapters in the books I recommended. And for example, the main reason I know of Chazelle's book it's because it is available for free online and stumbled across it a while ago. Btw, you seem knowledgeable. I have an algorithmic puzzle that has plagued me for some years now: Starting with an empty heap, and a sequence of inserts and min-pops, can you compute what elements will be left in the heap at the end in linear (expected) time? Obviously, you can't just run the instructions, that would take O(n log n) time. I have an algorithm to verify a proposed solution in linear time. But I don't have anything solid for finding one in linear time. I have a hunch that soft-heaps might be useful. And there's probably an even simpler probabilistic approach. Ideally, I'd like the solution in the comparison model, but if you have something that works on numbers only, that's also fine.
    - 6y ago
FiberBundle 6y ago
Probability and Computing by mitzenmacher is a very good book