2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you mean W=2^n, not N=2^n? $\endgroup$ – Yoshio Okamoto Mar 24 '11 at 22:44
  • $\begingroup$ @Yoshio: yes, sorry... fixed. $\endgroup$ – Fixee Mar 24 '11 at 23:02
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is the issue: the encoding. Why should some integers be input as binary (like W above) when others are given essentially in unary (like N above). The answer "because N is the number of items but W is an integer" doesn't really make sense to them. $\endgroup$ – Fixee Mar 25 '11 at 6:02
  • 1
    $\begingroup$ @Fixee: That's why you should mention the input size before you show the bound of $O(NW)$. Otherwise, students would feel cheated. $\endgroup$ – Yoshio Okamoto Mar 25 '11 at 10:28
  • $\begingroup$ Consider a similar problem: you have char array $A$ with $W$ cells and you have $N$ strings of various lengths. You want to store some subset of the strings in $A$ such that every cell is filled. This is (a thinly-disguised) SUBSET_SUM, and thus NP-Complete; explain why the running time is not $O(WN)$ now. The subtlety here is difficult to articulate... The answer has to do with "always use the most compact encoding for the input possible", but I've never seen that idea formalized... it must be done somewhere in complexity theory?! $\endgroup$ – Fixee Mar 26 '11 at 5:08
  • $\begingroup$ @Fixee: Excuse me, it's difficult to understand your problem. But, I can just say the behavior and the resource usage of an algorithm depend on how the input is encoded. For KNAPSACK, if the numbers are binary-encoded, the problem is NP-complete, but if the numbers are unary-encoded, the problem can be solved in polynomial time. You shouldn't assume the input is always encoded in the most compact way. But, you should specify how the input is given to you. $\endgroup$ – Yoshio Okamoto Mar 26 '11 at 12:41
7
$\begingroup$

Ask them to them implement the algorithm and then run it on a few dozen 12-digit numbers.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ excellent idea. I think I'll try it next time. $\endgroup$ – Suresh Venkat Mar 25 '11 at 10:14
  • 4
    $\begingroup$ I'm not sure if I understand correctly. That will show it takes long time, but doesn't answer the question whether $O(NW)$ is polynomial or exponential. $\endgroup$ – Yoshio Okamoto Mar 25 '11 at 12:11
  • 1
    $\begingroup$ Yep, running the original AKS primality testing algorithm ($O(n^{12})$) on a 12-digit number would probably take a while too, but it's a poly-time algorithm. $\endgroup$ – Fixee Mar 25 '11 at 15:40
  • $\begingroup$ @Yoshio: You're absolutely right, it doesn't answer the question. It's not meant to. The more important issue is to get the students to think about the question. O(nW) looks pretty fast, but the code is incredibly slow — What's going on?! $\endgroup$ – Jeffε Mar 28 '11 at 4:58
0
$\begingroup$

Imho this is one of the few key points in (TM) algorithmics that you have to accept, as it is a very dry fact with little to understand.

You could try to derive a contradiction from the students' wrong premise. By the same reasoning they apply to KNAPSACK, integer factorisation is in polynomial time and even reasonably fast. Why is it that common encryption methods can rely on factorisation being hard?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I've used that example. But I don't think it works to convince anyone. I actually like Jeff's idea and might try that next time. $\endgroup$ – Suresh Venkat Mar 25 '11 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.