Hacker News Reader

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

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

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

See eg https://jeffe.cs.illinois.edu/teaching/algorithms/notes/02-n...

And 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 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 But it's not for the faint of heart.

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.

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.

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

Fair enough! I still think it's a good recommendation, I was also adding on some thoughts on things that might be easier to digest :-)

> Chazelle also came up with the ingenious soft heaps.

Yes, soft heaps are very cool!

> I have an algorithmic puzzle..

Cool puzzle! Hmm, the solutions depend on exactly what you're asking.

The puzzle is substantially easier if the min-pop operation is not required to return anything. In this case, you are solving the much easier problem "return the top k elements of an array in unsorted order". You can insert into an unordered list and increment a counter every time min-pop is called. Then the last step can be done with a basic quickselect. See https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0908.pdf page 21, the "QuickSelect" algorithm. You need to do some small modifications to give you the "top k" elements rather than just the "kth" element. This gives expected linear time, and the note describes a deterministic algorithm that makes this worst-case linear time. You can implement deterministic quick select using soft heaps, or instead you could also do a radix sort and then slice out the popped elements.

If the min-pop operation is required to return the popped element, then I believe you run into the sorting linear bound that prevents a deterministic O(n) solution. (Surprisingly, this indicates the hardness of the problem is not really in the last step, it's in implementing constant-time insert and pop). I can't think of an immediate solution off the top of my head, but I don't think a soft-heap provides the right guarantees here. I also don't know of a probabilistic data structure that provides both insert and min-pop in expected amortized constant time, and it seems that this could be an area of research. There are some better, but not quite linear results outside the comparison-based model (https://cs.stackexchange.com/questions/6455/an-efficient-dat...)

The min-pop is not supposed to return anything, yes. We are only interested in the final contents of the heap. So no sorting required. You can eg give the results of the whole operation as a bitmap over the inserts, so you need to return a linear number of bits.

Min-pops and inserts will in generally be interleaved. The prototypical example has blocks of 2 inserts and 1 pop repeated n times. (All other interleaving patterns can be reduced to this one in linear time.)

QuickSelect doesn't work for this.

QuickSelect or Median-of-Medians approaches work if you only have a small constant number of interleaved blocks (of any arbitrary internal length). Like eg all the inserts first then all the min-pops is equivalent to finding the k smallest elements.

Probability and Computing by mitzenmacher is a very good book

Eric Lippert did a nice blog post on this sort of thing a few months ago: https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/

The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

I think one of the main takeaways of his post is that anything is survivable when n is small, and that the overhead required to spool up more robust data structures just isn't worth it for small n.

I often find that the actual number that could be called “Small” in this sense is often quite large. Computers are very fast these days.

> The other points he mentions, beyond constant factors, are that algorithms with great theoretical characteristics tend to interact really poorly with gross real-world considerations like the memory hierarchy, and that worst-case performance is not average-case performance.

I'd say _some_ algorithms and data structures with great theoretical characteristics tend that way. Just as many other work great in practice as well. You have to measure and benchmark.

Exactly this. While the underlying theory is excellent on many of these theoretical algorithms, they typically don't perform as expected when taking into account the infinite complexities of the real-world.

But being able to understand the core value of the algorithm enables you to adapt or modify slightly in order to get it to work as needed in the real world.

In general just knowing that there are specialized algorithms for certain classes of problems is 80% of the expertise you gain over years of experience. Knowing that things like Bloom filters exist when you hit a problem that could be solved by this class of algorithm gets you much further than expertly memorizing any specific implementation of the algorithm. There are a variety of them depending on the actual use case you are looking to solve for.

At Caltech, we'd call that "brute force and ignorance" which is often the best solution.

For example, Enzo Ferrari once said that the secret to better performance is more horsepower.

The actual quote was something like "aerodynamics are for people who can't build engines" which proves your point a bit better.

It's actually a bit ironic, because I consider Ferrari to build elegant cars while my old V8 Dodge is a triumph of brute force and ignorance. They're both great cars at opposite ends of the spectrum :-)

A variation on the sentiment I heard in a movie: "turbochargers are for wussies, real cars have cubic inches!"

Elegant doesn't always go with optimized aerodynamics.

Well, I was using less horsepower.

The problem in the previous solution was that it took a while to keep the fancy datastructures updated. (It's a globally replicated distributed system..)

Due to the physical architecture of CPUs/etc., data structures that have "worse" asymptotic performance are often quite a bit faster than those with "better" performance. For example, iterating through a small array to find an item and test for existence is often quite a bit faster than using a hash set for the same operation.

In the same vein, pre-processing your data via sorting on some carefully chosen keys can sometimes alleviate the need for purpose built data structures.

And because of caches, sorting can sometimes beat hashtables.

Which is why I just use the standard library.

Most languages have more than one data structure in their standard library.

Algorithms are all about eliminating waste effort. Not using programs invented by others to manipulate data structures. Those just happen to be solutions to some problem patterns.

A person good at algorithms is some one who can make things happen with least effort possible. Not some one who can invert trees, even more so when there is not need to invert a tree.

You can see how good some one is at algorithm stuff to see how much drudgery exists in the way they do work themselves.

I've learned approaches like this when I took a Operations Research class. I found it all exciting. We've also learned techniques to better choose between meta-heuristics like CGRASP, or flat algos, or integer programming, and so on. Now I'm seeing if I can think of some cool pet project where I can apply this stuff.

Oh, I also applied lots of linear and integer programming.

The main benefit of something like integer programming is that you get a clear separation of the specification of your solution and the algorithm that computes it.

When even smart people naively attack any kind of optimization (or selection) problem, the resulting approach often mixes the business logic for specifying the optimum solution and the code for finding that optimum.

That makes any change in business requirements very hard to implement.

It doesn't matter how well you can optimize if you don't measure in production and benchmark!

A lot of algorithms and data structures are not cache aware and assume that all memory operations have the same cost.

It's sometime best to use the 'worst' approach that allows most data to be as close to the CPU as possible for the longest.

Nested loops go brrrrr

No loops in this program. It's all written in Erlang, so it's (tail) recursion all the way.