williamkuszmaul
Joined 10 years ago
Karma
591
Submissions
59
Member since
Nov 19
Recent submissions
Comment · 3 years ago
Overall seems like a great book. The hashing chapter is a bit half baked though. It claims without reservation that deletions simply cannot be efficiently implemented with linear probing. But there are at least two two efficient to do this (lazy deletions or just fix up the hash table), and both are worthwhile for students to know.
Comment · 3 years ago
1/100 is too large of a cutoff imo. If you have a class of 96 students, there's a decent chance that an innocent student gets flagged for no reason. I hope he lets the student on the bubble off the hook.
Comment · 3 years ago
One thing I'm confused about: Did the author try vectorizing the linear search implementation? (Of course, it is possible that even if they did not, the compiler did.) I would imagine that vectorization is behind the advice to use linear searches on small arrays.
Comment · 3 years ago
Related recent paper in Science:
https://www.science.org/doi/10.1126/science.aam9744
Comment · 3 years ago
One important caveat: it is widely believed that randomization does make a big difference for data structures problems. For example hash tables (which use random hash functions) take O(1) time per operation, but it is conjectured that no deterministic data structure can match this.
There are also problems in online algorithms where randomization provably changes what is possible, for example the "cup game problem." (https://arxiv.org/abs/1904.02861)
Finally, although randomized primality testing (1970s) is often credited as the start of randomized algorithms as a field, it's worth noting that hash tables (1954) and quick sort (1961) were much earlier.
Comment · 4 years ago
I think it would be fair to say that it's a kind of funny trie-hash-table hybrid. What's neat though is that it manages to achieve better space bounds than either a trie or a hash table would on their own.
I didn't invent the algorithmic idea --- it's basically a simplification of a data structure that was published in ICALP 2003 [1]. As far as I know, the idea of combining hash tables and tries in this kind of way (despite being incredibly simple!) doesn't appear in either the theoretical or experimental literature prior to that.
I'd be interested in any other earlier sources that people might have.
[1] Raman, Rao. Succinct Dynamic Dictionaries and Trees. https://link.springer.com/chapter/10.1007/3-540-45061-0_30. ICALP, 2003.
Comment · 4 years ago
But does the question ever say "all"...?
Comment · 4 years ago
Unless I'm misreading, the question as stated in the blog post never says there is only one duplicate (there might be many!), so in that sense I think his answer may be wrong. A more robust solution is just to have an array of n counters and just count how many times each item appears.
Comment · 4 years ago
Using 64 bit integers, we can store the square of any 32 bit integer. Not that small...
Comment · 4 years ago
Impressive!
There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those...
Also, since we are sorting integers, I'd also be interested to know how well a modern implementation of radix sort can be made.
Comment · 4 years ago
If the coin were unbiased, we could compute the exact probability of getting 10231 or more heads with 20000 flips as:
"sum (20000 choose x)/2^20000 for x from 10231 to 20000",
which Wolfram Alpha evaluates to 0.00056.
The probability of getting a number of flips that differs from 10000 by at least 231 is twice that, so about 0.001.
So, in fact, the probability of this happening by dumb luck is about 1/1000. That's pretty strong evidence.
Comment · 4 years ago
From what I've heard, Perci Diaconis (one of the authors of the original paper) actually could do this. He was a magician before he became a mathematician, and a lot of his early mathematics work focused on math relating to the magic tricks he used to do