Resources to learn Dynamic Programming, NP Complete, Knapsack Problems, and more on Algorithms

Question

What are the good resources that discuss Algorithms, P NP problems, Dynamic Programming, Special cases of those- Knapsack problems and such.

The resource must have working code, preferably in Python. Advantage if it explains some of the TopCoder SRM Dynamic Programming questions.

PS: I am a web developer interested in algorithms and and am now trying to look into some formal and complete material on the subject.

Does SICP discuss these?

Answer 1

No, SICP wouldn't be the right place. It may mention them, but the best reference on this is Introduction to Algorithms which you may hear referred to as "CLR", though I guess now it's CLRS. No working code in this, just a pascal-like pseudocode.

Answer 2

I guess that if you are intrested in Dynamic Programming, you should look at Introduction to Algorithms.

But generally speaking, it is a technique in Optimization Theory/Operation Research areas. There are more techniques such as Linear Programming, Interger Linear Programming etc. If you are intrested in them, look for Introduction to Operation Research by H.Taha

Answer 3

Algorithm Design by Kleinberg and Tardos is a very well written book, but uses pseudo code.

Answer 4

If you want a crash course in Dynamic Programming, try Project Euler... Problems 208 and 215 spring to mind as requiring DP. If you get hooked to it as most of us do, you'll find yourself learning more mathematics, algorithms and advanced programming than any formal course could provide you, and even better, having fun along the way. The best part is, once you solve a problem, you have access to other people solutions, and reading through them is extremly instructive.

And then of course you have wikipedia...

Answer 5

Another resource you can look at is Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.

It is a relatively recent book, and hence not one of the 'classics', but it is a good job of teaching algorithms from the ground up. The last few chapters look at "Dynamic Programming", "Linear programming and reductions", "NP-complete Search Problems" and "Coping with NP-completeness" - so exactly what you want. The code annotations are in pseudo-code, and are all cleanly reimplemented.

The primary advantage of this book is the authors distribute it's penultimate draft free on their site. I'm a new user and can't post hyperlinks, but google "algorithms vazirani" and it's the first and second link.

In regards to looking for working code "preferably in Python", I think that's the wrong approach, especially in algorithms. Implementing the algorithms yourself is a vital step in both learning the algorithm and feeling comfortable with the language. If you haven't yet worked out how the algorithm works, it's far better to actually look at the algorithm's steps rather than trying to find the algorithm's steps in the program's implementations.

After you learn these algorithms and techniques a great deal of the TopCoder problems can be sorted into a few sets, each expanding off of one idea or another. Once you're done with a more theoretical approach, you could move on to something like Programming Challenges by Steven S. Skiena and Miguel Revilla. It has a far briefer look at the algorithms themselves, instead focusing more on what sorts of competition problems can be solved by which of the standard algorithms. Almost always the solution to competition problems are re-imaginings or extensions of the original algorithms.

Answer 6

If you don't restrict yourself to code only, the primary reference for NP is Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness

http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455

Answer 7

Theoretical Side (P=NP?) : Introduction to the Theory of Computation, Sipser

Algorithmic Side (Dynamic Programming et al.): Introduction to Algrithms, Corment This is not python specific, but you can't ignore this.

Answer 8

Well, you've binded together some different topics:

1. Algorithms is a really huge topic, so I assume that you're talking about some basic background on that argument. The immortal Cormen should give you a good "introduction".
2. P, NP, etc. are elements of a complexity hierarchy. Those are subject of Computational Complexity, a fascinating and theoretically-intensive field of computer science. A formal training in those subject is a challenging job, because it's a mathematically rich area (the halting problem is a reformulation of the Goedel's incompleteness theorem...); I have to note that NP-hard and NP-complete is often used as a cool word to just say "it's difficult to solve in an efficient manner", not in their formal meaning...
3. The Knapsack problem is an optimization problem in the field of Operational Reseach. The Cormen book cover a little of that (huge) field.

So, if you want a decent coverage of those things, you have to invest your time in three different (and vast) topics.

Answer 9

If you're not afraid of C/C++/Pascal, Solve every USACO problem in a row. It is designed to prepare students for Informatics Olympiads, what should give you great understanding of the most popular algorithms, data structures. The solutions are secret until you solve the problem, however you can easily google them if you want.

An alternative for USACO is UVa Online Judge. It accepts java as well as C/C++/Pascal and has a larger and newer set of problems. The disadvantage of it that the material is structured worse than in USACO. Also, last time I checked, it was slower and did not give helpful responses if the submission was incorrect.

If you like reading books instead solving stuff, you can try "Algorithm Design Manual", by S.Skiena, though examples there are basically in C. I like this book, because it also contains "War stories" - how algorithms are applied in real life, and a bunch of interview questions as well as basic maths required to understand the algorithms.