NP & Dynamic Programming
NP Complete
Think of any problem you like, it could be adding two numbers together or determining the number of your friends that will show up to your birthday party. I am sure it'll be different than last year. You just had bad timing, since your birthday fell in the middle of a spring break trip, and they just forgot to invite you. Not a big deal.
Any problem you can think of is in a class of problems. Likely, you picked a problem in the P realm, which is to say a computer can solve it relatively quickly. Addition, for example, falls into this category. You can even think of something that a human, like what your mother and father, your siblings, your friends, pretty much anyone you know, barring yourself, can do quickly. If you had to find someone who was older than you, you could likely do this fairly quickly. Finding someone who weighed more than you, someone who was ugli...well.
There are a set of problems which a computer cannot solve quickly, but they can quickly check the answer. Sudoku, is a great example of an NP problem. A computer can solve a sudoku puzzle in a 9X9 grid, relatively quickly, but the time becomes much worse as the grid becomes larger. Now, if a problem cannot be solved by a computer quickly, then we cannot check an answer quickly right?
Wrong! As per usual. Given an incorrect solution to Sudoku, a computer can check it very quickly. Unfortunately, my Sudoku checker is not currently working. I think it has to do with the processor, since I know the code is right, and there is no way I did not correctly solve the puzzle, it was in a children's book. And I am part of MENSA, so...
Not all NP problems have answers which can be checked relatively quickly. If an answer takes a long time to compute, then the problem is considered NP Hard. The interesting thing about solving an NP problem is that once you quickly solve one of them, the whole class of NP problems will be easy to solve. This is sigificant because things like protein folding are NP problems, and solving that would help us cure cancer. I was thinking about working on it, but I decided that my time would be better spent helping you. See what you did? All because you want to be a programmer....
This video is a longer, less interesting version of what I just explained:
P V.S. NP and The Complexity Zoo
Dynamic Programming
If you had to mutliply big numbers together, how would you do it?
You would probably multiply portions of the numbers together, then other
portions, and then add all of your results together. So, let's do this.
Let's multiply really big numbers together. How about 34, and 34. I
know you are scared! But we can do this. I mean, I can. And you can watch.
First we do 4 * 4
Next 4 * 3
Next 3 * 4
Next 3* 3
3 * 4 and 4 * 3 are the same thing, so we are doing double the work. Instead, we should just remember that is 12, so when we see it again we can immediately remember the answer. Well, I won't expect you to remember that, but you could get a computer to remember it. That is the idea behind dynamic programming. You break a problem down into the simplest possible sub-components. Then, you solve each of those sub parts, saving the data as you go along. If you ever encounter that problem again, you already know the answer!
What is the difference between top down and bottom up? Dynamic programming is the process of picking what order your computations will go in, and working these values into the future of the algorithm. Top down- you start at the top and break the problem down until you are at the base level. Top down cannot be coded until the whole problem is understood, but this gives the problem a clear direction. Memoization is a key feature of the top down approach. You track the work that you have already done, and cache those values. If you have a cached value, then you use the pre computer answer. Bottom up- you start with small examples and build these examples up into larger and larger parts. You can begin programming bottom up problems immediately, but can cause a problem if you don’t know how the problems are going to fit together.