When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.But when we get to knapsack and solve it via DP, they are confused.  For example, the conventional approach to knapsack for $N$ items and a $W$-capacity bag  is the straightforward $O(NW)$ DP method.  But I then point out that $W=2^n$ and therefore DP is exponential time.  This invariably causes objections, confusion, and lots of doubt.  I have yet to find a way of explaining this that makes it clear.  Can anyone help?Oh, and they haven't seen Turing machines, so that's off-limits.
Explaining input-size of integral arguments to undergraduate CS students
soft question;time complexity;teaching
As far as I understand, the question is concerned with teaching.One idea would be to mention the input size explicitly just after describing the problem specification and before going into an algorithmic solution.There might be some discussion among students on what should be the input size, but this is fine.  Then, students would find out the behavior (and the resource usage) of an algorithm could depend on how the input is given and how the input size is measured.  Such examples are abundant, and so you can introduce some of them to students (as a reference, not in a classroom).  If you're going to discuss NP-completeness, you can mention that KNAPSACK is NP-complete if input numbers are binary-encoded, but not if they are unary-encoded.