What is the difference between a polynomial and a pseudo-polynomial algorithm?

A polynomial time algorithm has running time polynomial in the length of the input. A pseudo-polynomial algorithm, on the other hand, takes time which is polynomial in the length of input if input written in unary form. As pointed out, this is same as polynomial in the numeric value of the input. Classic examples of pseudo-polynomial time algorithm include dynamic programming for Knapsack Problem and Bin Packing.

If [math]\Pi[/math] is a problem, and [math]I[/math] is an instance of the problem, then a polynomial algorithm solving [math]\Pi[/math] operates in time polynomial in the binary representation of [math]I[/math]. For example, suppose I wish to determine whether a given number [math]n[/math] exhibits a certain property. A polynomial algorithm solving the problem will run in [math]O(m^k)[/math] time for some [math]k[/math], where [math]m[/math] is the length of the binary representation of the input [math]n[/math] (in this case [math]m = \lfloor \log_2 n \rfloor + 1[/math]). A pseudo-polynomial algorithm solving a problem [math]\Pi[/math] operates in time polynomial in the unary representation (numerical value) of the input [math]I[/math]. In our example above, a pseudo-polynomial time algorithm will have running time [math]O(n^k)[/math], since [math]n[/math] is the length of the unary representation of [math]n[/math] ([math]\underbrace{111...1}_\textrm{n}[/math]). Now that we understand the definitions, the question is why do we care about algorithms that run in time polynomial in the numerical value of the input? Our computers represent data in binary! Well, it turns out the pseudo-polynomial time algorithms are very useful in constructing a PTAS (polynomial time approximation scheme) for certain ([math]NP[/math]-complete) problems. Why is that? 1. The numerical value of the input grows linearly with the input value, meaning that our metric for the size already grows pretty quickly — so that the extra steps algorithms may need to produce a solution does not "add much" to the already speedy increase of the metric. Therefore it is easier to find algorithms that operate in pseudo-polynomial time. 2. Once we come up with pseudo-polynomial time algorithms, we can use them to efficiently solve problems where the unary representation is guaranteed to be bounded by a polynomial in the binary representation. (For example, consider the Knapsack problem, but with the restriction that the profit associated with each item is bounded by a polynomial in the total number of items available. We can use a pseudo-polynomial time algorithm to solve this problem efficiently.) 3. In the cases where the no polynomial bound on the value exists (such as with general [math]NP[/math]-complete problems) we can translate an instance of a problem [math]I[/math] into a new instance [math]I'[/math] that is bounded in the desired way, suffering a modest and controlled error in the process (since we are in way ignoring some least significant bits of the input in order to compress it).  This means that we can approximate, with a controlled error parameter, solutions to problems that we otherwise have yet to solve efficiently! That is exactly how, for example, we found algorithms finding solutions to the Knapsack problem that come arbitrarily close to the the optimal solutions, i.e. [math](1-\epsilon)OPT[/math], where the algorithms operates in time polynomial in both the size of the input and [math]1/\epsilon[/math]. Hooray!