<p>As far as I understand, the question is concerned with teaching.</p>

<p>One idea would be to mention the input size explicitly just after describing the problem specification and before going into an algorithmic solution.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-25T06:02:26.557Z
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.
Fixee
CC BY-SA 2.5
2011-03-25T10:28:06.943Z
@Fixee: That's why you should mention the input size before you show the bound of $O(NW)$.  Otherwise, students would feel cheated.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-26T05:08:00.403Z
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?!
Fixee
CC BY-SA 2.5
2011-03-26T12:41:49.070Z
@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.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-25T01:26:24.973Z
2011-03-25T01:26:24.973Z
Yoshio Okamoto
<p>Ask them to them implement the algorithm and then run it on a few dozen 12-digit numbers.</p>

CC BY-SA 2.5
2011-03-25T10:14:31.030Z
excellent idea. I think I'll try it next time.
Suresh Venkat
CC BY-SA 2.5
2011-03-25T12:11:16.607Z
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.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-25T15:40:09.940Z
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.
Fixee
CC BY-SA 2.5
2011-03-28T04:58:24.360Z
@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?!
Jeffε
CC BY-SA 2.5
2011-03-25T03:50:04.577Z
2011-03-25T03:50:04.577Z
Jeffε
<p>Imho this is one of the few key points in (TM) algorithmics that you have to <em>accept</em>, as it is a very dry fact with little to <em>understand</em>.</p>

<p>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?</p>

CC BY-SA 2.5
2011-03-25T10:14:05.523Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-03-24T22:29:01.450Z
2011-03-24T22:29:01.450Z
Raphael
<p>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.</p>

<p>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?</p>

<p>Oh, and they haven't seen Turing machines, so that's off-limits.</p>

CC BY-SA 2.5
2011-03-24T22:44:41.130Z
Do you mean W=2^n, not N=2^n?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-24T23:02:00.363Z
@Yoshio: yes, sorry... fixed.
Fixee
<soft-question><time-complexity><teaching>
Explaining input-size of integral arguments to undergraduate CS students
Fixee
# Explaining input-size of integral arguments to undergraduate CS students

(Asked by: username_0 on 2011-03-24)

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.

**Tags:** soft-question, time-complexity, teaching

> **Comments:**
> **username_1**: Do you mean W=2^n, not N=2^n?  
> **username_0**: @Yoshio: yes, sorry... fixed.  

---

## 3 answers

### Answer by username_1 on 2011-03-25. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0: That's why you should mention the input size before you show the bound of $O(NW)$.  Otherwise, students would feel cheated.  
> **username_0**: 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?!  
> **username_1**: @username_0: 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.  

---

### Answer by username_2 on 2011-03-25. Score: 7

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

> **Comments:**
> **username_3**: excellent idea. I think I'll try it next time.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: @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?!  

---

### Answer by username_4 on 2011-03-24. Score: 0

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?

> **Comments:**
> **username_3**: 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.  

---

