Viewing profile — williamkuszmaul

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 p…

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 t…

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 imag…

Related recent paper in Science: https://www.science.org/doi/10.1126/science.aam9744

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) ta…

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 …

But does the question ever say "all"...?

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 mo…

Using 64 bit integers, we can store the square of any 32 bit integer. Not that small...

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 s…

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", whic…

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 m…

I think that many "software companies" are actually marketing companies that plan to make almost all of their profit from a product that has already been built. They're not necessa…

This is neat! Some if the alternative solutions discussed here seem to confuse compilation with evaluation. Fortran is trying to rewrite the computation in such a way that, later o…

In case anyone is wondering, the only role of covid here is that shutdowns prevented technicians from being able to fix the issue in person.

One of the things that's cool about Bzip is that it makes use algorithmic techniques developed by theoretical computer scientists in order to perform the Burrows Wheeler Transform …

One estimation trick that I've found effective is the following: (1) determine the smallest number that your sure is larger than the true answer. (2) determine the largest number t…

MIT recently cut all of their relationships with Elsevier journals. Researchers are still allowed to publish in Elsevier, but when they do, even they won't have access to their own…

I'm not sure why they claim that the total time grows quadratically. If tasks arrive arrive randomly at the same average rate as they can be processed, then the amount of time that…

It's even worse than most people seem to realize. For many years the ISO standard for C included the line: "If both operands are nonnegative then the remainder is nonnegative; if n…

Another example of this would be if there are three candidates X,Y,Z. Suppose Alice strongly prefers X and Bob strongly prefers Y. Rather than each of Alice and Bob allocating 100 …

It turns out that if you write down on the list of requirements that you would want from a voting system in order for it to be fair, the no deterministic voting system is fair. Thi…