Have you ever realized you can't solve the homework you assigned?

Question

This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.

This has happened to me a handful of times in my 12-year career as a professor: I hurriedly assigned some problem from the text thinking "this looks good." Then later realized I couldn't solve it. Few things are more embarrassing.

Here's a recent example: "Give a linear-time algorithm that determines if digraph $G$ has an odd-length cycle." I assigned this thinking it was trivial, only to later realize my approach wasn't going to work.

My question: what do you think is the "professional" thing to do:

• Obsess on the problem until you solve it, then say nothing to your students.
• Cancel the problem without explanation and move on with your life.
• Ask for help on cstheory.SE (and suffer the response, "is this a homework problem?")

Note: I'm looking for practical and level-headed suggestions that I perhaps haven't thought of. I realize my question has a strong subjective element since handling this situation involves one's own tastes to a large extent, so I understand if readers would prefer to see it not discussed.

Answer 1

Yes, sadly, I've done this several times, as well as the slightly more forgivable sin of assigning a problem that I can solve, but only later realizing that the solution requires tools that the students haven't seen. I think the following is the most professional response (at least, it's the response I've settled on after several false starts):

1. Immediately and publicly admit the mistake. Explain steps 2 and 3.
2. Give every student full credit for the problem. Yes, even if they submit nothing.
3. Grade all submitted solutions normally, but award the resulting points as extra credit. In particular, give the usual partial credit for partial solutions.

The first point is both the hardest and the most important. If you try to cover your ass, you will lose the respect and attention of your students (who are not stupid), which means they won't try as hard, which means they won't learn as well, which means you haven't done your job. I don't think it's fair to let students twist in the wind with questions I honestly don't think they can answer without some advance warning. (I regularly include open questions as homework problems in my advanced grad classes, but I warn the students at the start of the semester.) Educational, sure, but not fair.

It's sometimes useful to give hints or an outline (as @james and @Martin suggest) to make the problem more approachable; otherwise, almost nobody will even try. Obviously, this is only possible if you figure out the solution first. On the other hand, sometimes it's appropriate for nobody to even try. (For example, "Describe a polynomial-time algorithm for X" when X is NP-hard, or if the setting is a timed exam.)

If you still can't solve the problem yourself after sweating buckets over it, relax. Probably none of the students will solve it either, but if you're lucky, you'll owe someone a LOT of extra credit and a recommendation letter.

And if you later realize the solution is easy after all, well, I guess you screwed up twice. Go to step 1.

Answer 2

I'm not a teacher yet, but as a TA, I once did this.

I didn't find the problem in a textbook; instead, I came up with the problem myself. It turned out that, in spite of looking innocent, the problem had been the subject of a lot of debate back in 1980s, but was settled then.

Well, after knowing that, I announced that solving that problem has extra credit. No one came up with the correct result, but I gave half the (extra) mark to those whose answers were reasonable. Then, in the class, I admitted that this had been indeed a hard problem, and pointed the students to the relevant history.

PS1: The problem was about the DES cipher: Are there a plaintext (P) and a ciphertext (C) such that, for two distinct keys K1 and K2, DES enciphers P to C under both keys? That is, C = DES(P, K1) = DES(P, K2).

The answer seemed to be "NO," but turned out that was not the case. See the relevant research here: How easy is collision search? New results and applications to DES.

PS 2: The Immerman–Szelepcsényi theorem has been proved in much the same way! Quoting from Lipton's blog:

There is one more comment I must add. Robert [Szelepcsényi] was a student when he solved the problem. The legend is that he was given a list of homework problems. Since he missed class he did not know that the last problem of his homework was the famous unsolved LBA question. He turned in a solution to the homework that solved all the problems. I cannot imagine what the instructor thought when he saw the solution. Note, it is rumored that this has happened before in mathematics. Some believe this is how Green’s Theorem was first solved. In 1854 Stoke’s included the “theorem” on an examination. Perhaps we should put P=NP on theory exams and hope ...

Answer 3

I've been on the other side of this I'm sure.. However, sometimes it isn't really necessary for there to be an answer to have students learn. The process of trying many different approaches to solving a problem is often more important than the outcome.

Personally, I would go to class the next day and say I don't expect that many of you got the answers but let's talk about what steps you used to try to figure it out. If that isn't a real world type of question I don't know what is(used by many job interviewers).

We sometimes get side tracked with learning facts and getting answers that we don't talk about the process which in itself can tell you more about where your students (or even you) are. -j

Answer 4

One of my professors in graduate school assigned a problem he later realized he couldn't solve. He emailed everyone explaining the situation and turning it into an extra credit problem. It really motivated me to solve it (which took hours), but it was a lot of fun.

Answer 5

I'm a TA.

I think you should "Obsess on the problem until you solve it". Afterwards, simplify it such that parts of it or hints can be handed out. As one example, the simplification step could be to divide the problem into small subproblems and these subproblems can be then be given as subquestions to the original. For your example-question that could be as simple as "reduce the problem to another O(n)-problem that we have just taught you how to solve" and "prove that it is a linear time reduction".

With programming exercises there can often be some boilerplate that they wont learn that much from, which can be handed out as skeleton-code. On an Operating Systems class we recently posed the assignment "Implement a FAT32 driver in your kernel" (which they had created over the previous course-assignments). That required way more code than we expected, so we handed out a lot of code handling FAT access, that actually made some students do it. Such a huge assignment was of course an error, so next year we will probably try with ext2 or MINIX. Those who did the majority of the assignment really enjoyed that it was a realistic file system which they themselves had used. Those who only did parts of it (e.g. only just realised they had to endian-conversion) also got it approved.

So my suggestions are: Hand out subquestions, hints and skeletons. Be lenient when correcting.

Answer 6

This answer is possibly as useful as a stable door, but it's for this reason that I have a rule never to set homework exercises that I haven't already solved myself. This is not only so that I know it's solvable, but also to check that it's the right length and level - I implemented this rule after once or twice getting caught with setting questions that were too hard or required things that the students hadn't done yet.