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).
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.)
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 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.
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.
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...)
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.
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.
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.
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.
For example, Enzo Ferrari once said that the secret to better performance is more horsepower.
A variation on the sentiment I heard in a movie: "turbochargers are for wussies, real cars have cubic inches!"
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..)
And because of caches, sorting can sometimes beat hashtables.
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.
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's sometime best to use the 'worst' approach that allows most data to be as close to the CPU as possible for the longest.
The programme in question was running into performance problems, and a few smart people had already banged their head against a wall solving them.
After lots of experiments and different approaches, my solution was to remove most of the advanced data structures that were in the code.
In theory, they should have given us logarithmic runtime on some common operations, but the constant factors were too large. I proved (in the mathematical and the practical sense) that a brute force scheme combined with a careful randomization would dramatically improve real world performance with a fraction of the previous line count.
Despite me removing those interesting data structures, I still count it as a great application of my algorithms-and-data-structures knowledge: a big part of expertise is to be able to spot opportunities for simplification.