3 ms·
I feel your pain. I did exactly one dynamic programming algorithm (in the string matcher for Hyperscan) and was pretty inordinately pleased with myself for doin
by glangdale 8y ago
I feel your pain. I did exactly one dynamic programming algorithm (in the string matcher for Hyperscan) and was pretty inordinately pleased with myself for doing it, but we built dozens of algorithms in that project and that was the only case of DP that I recall.
But I expect to go into interviews and have people demand a different rain dance, now that everyone is talking about DP. They like mugging people with 'so big it has to be out of core' stuff, which is a good way of finding out who went to the right grad school algorithms course. :-)
- vkazanov 8y agoI think I only saw DP-based algorithms 3 times in 12 years of working and reading open source code. Two of them were boring textbook-based implementations. One algorithm was original, and came from 80s - it's from Emacs source code, with comments like "do not touch", "here be dragons", etc.
- glangdale 8y agoYes, the code involving the DP algorithm I put in had a bug in it - not from the DP algorithm itself but the assumptions that fed into it - which went undetected for some time because of how complex the DP algorithm was and how hard it was to evaluate. It only caused a minor performance quirk (not a actual semantic error) so was hard to find. A cautionary tale about being overly clever-clever I suppose.