How to Design an Algorithm (2018) | Hacker News Reader

How to Design an Algorithm (2018)

adamconrad.dev

85 pointsrohithkp12 comments

Open articleView on HN

Whoa! Now I know where the newsletter signups came from :)

Hello HN - author here. Yes, I did audit this entire course over the fall of 2018 (edited again in 2019).

In fact, very soon I will have a podcast episode out with Prof. Skiena to talk about his book and the course.

Any questions or comments you want to shoot over please reach out!

The book to go along with this course - The Algorithm Design Manual (https://amzn.to/3iEs48r)

Wasn't there a new edition of the book coming soon?

Isn't the Knacksack problem hard and unsolved problem?

Solving the Knapsack problem is pretty easy, it's probably the textbook example for explaining branch-and-bound algorithms. What you probably had in mind is that it's NP-complete, meaning that we don't know any polynomial-time algorithms and most experts think that none can be found, although nobody has been able to prove that (this is the famous P=NP? problem).

Which is why the OP says: > Find counterexamples to each of the following algorithms for the knapsack problem.

Anyway, yes, in the strictest sense of the term, it is unsolved because it's NP-complete, however it's been thoroughly analyzed in many different ways (it's pseudo-P, we have a MITM algo, different flavors of approximations, etc.)

NP-complete doesn't mean unsolvable! It means that we don't know any algorithms that run in subexponential time for every input. But of course we can use the algorithms with exponential worst case running time. We can also use algorithms that solve most instances fairly quickly but may take a very long time to solve some particularly hard instances.

Yes, I don't disagree with any of this. Let me rephrase that. The problem of determining what is the minimum asymptotic time complexity for an algorithm that correctly solves any knapsack instance is unsolved.

Exponential != Super-polynomial

There exist np-complete problems with known super-polynomial, sub-exponential solutions. The stable set problem for planar graphs is an example.

Actually, the knapsack problem allows taking an item more than once. The problem described in the blog is the 0-1 knapsack problem which can be solved in polynomial time.

0-1 knapsack is not known to be solvable in polynomial time.

Okay, to be pedantic, pseudo-polynomial time.

Reply on news.ycombinator.com