3 ms·
In Memoriam: David S. Johnson
- pklausler 11y agoThis is the co-author, with Garey, of that great 1979 book on NP-completeness, which begins with a really practical reason for knowing about such things: being able to prove to your boss that the problem you've been told to solve is at least as hard as some other problems that people smarter than you haven't figured out.
- ehudla 11y agoAgain, the passing of one of CS heroes. /Computers and Intractability/ was one of the first CS books I bought. The anecdote they open with, about coming to your boss claiming "I can't find an efficient algorithm, I guess I'm just too dumb" (as opposed to proving that the problem is NP-complete: "i can't find an efficient algorithm, but neither can all these famous people") is still one of my favorite teaching stories.