Algorithms Illuminated (Part 4): Algorithms for NP-Hard Problems

Algorithms Illuminated #4

by Tim Roughgarden

Fourth book in a series that provides an accessible, no-nonsense, and programming language-agnostic introduction to algorithms. Includes hints or solutions to all quizzes and problems, and a series of YouTube videos by the author accompanies the book. Part 4 covers algorithmic tools for tackling NP-hard problems (heuristic algorithms, local search, dynamic programming, MIP and SAT solvers) and techniques for quickly recognizing NP-hard problems in the wild.

Genres: Computer Science, Algorithms, Programming, Textbooks

273 pages, Kindle Edition

Published July 15, 2020

Reviews

[Сергей Польшин · Rating 5 out of 5]

Good as always

I think it's book cover 100% of possibilities to work with np hard problems.
But better to have more real life examples like with frequences.

[Anthony O'Connor · Rating 4 out of 5]

Excellent finale

An excellent finale to an excellent series. A bit rushed in some places maybe but it cleared up a few major points for me. So that was great. The author did decide to redefine NP in terms of search problems. He made it clear that he was doing so. And maybe it should have been done that way originally. But it wasn’t. You can’t say everyone else calls it a duck but I’m going to call it a dog. That’s just confusing. For this faux pas he gets a four rather than a five.

[Heather Fryling · Rating 4 out of 5]

This whole series is fantastic for those wanting to gain a deep understanding of algorithms. The one drawback is that there are no solutions for most of the problems.

[Aaron Zhu · Rating 5 out of 5]

This is the clearest and most intuitive introduction to algorithms for NP-hard problems out there! My favorite parts: the description of the Bellman-Held-Karp Algorithm, the chapter on the FCC Incentive Auction, the list of "acceptable inaccuracies" about NP-hardness, and the reduction diagram in Chapter 19.