36
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 13
    $\begingroup$ In this case, I'd recommend obsessing until you solve it ... I suspect the problem isn't all that hard. But if you can't solve it, the professional thing to do is confess this to the students, and either cancel it or (as recommended in Sadeq's answer) make it extra credit. $\endgroup$ – Peter Shor Apr 21 '11 at 19:08
  • 21
    $\begingroup$ A digraph has an odd cycle iff at least one of its strongly connected components is non-bipartite as an undirected graph. So if you've already talked about both strong connectivity and bipartiteness, this still might make a good exercise. $\endgroup$ – David Eppstein Apr 21 '11 at 20:49
  • 3
    $\begingroup$ We had a similar case in our complexity course this semester: prove that Linear Integer Programming is NP-complete. The difficult part is showing that the problem is in NP (see C. Papadimitriou, "On the complexity of integer programming", 1981). $\endgroup$ – Kaveh Apr 21 '11 at 22:47
  • 5
    $\begingroup$ @Fixee: I don't think it's as terrible or embarrassing as it looks. You can simply put a note on the course website saying that the problem was harder than what you expected. Then either revise the problem, give more hints or make it a bonus question. Science is full of uncertainty, so a little bit of uncertainty in the course is fine! :-) $\endgroup$ – Dai Le Apr 22 '11 at 1:50
  • 4
    $\begingroup$ Whatever you do, be honest and do not punish students for your mistake. Btw, we got exercises that were actually unsolvable for subtle reasons once. The points were removed from the total achievable sum but awarded points counted. $\endgroup$ – Raphael Apr 22 '11 at 19:46
28
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This is a great answer. My approach in the past has always been a little different: I'll obsess until I solve the problem, then give strong hints. Sometimes, out of guilt, I'll give away the answer as a "hint" with the apology that "the problem was a bit harder than I had intended". $\endgroup$ – Fixee Apr 24 '11 at 20:08
18
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Nota: Immerman's first name is Neil. Szelepcsenyi's is Robert. $\endgroup$ – Michaël Cadilhac Apr 21 '11 at 18:57
  • 3
    $\begingroup$ Lipton's quotation is great! $\endgroup$ – Lamine Apr 22 '11 at 8:10
  • 2
    $\begingroup$ "An event in Dantzig's life became the origin of a famous story in 1939 while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue" $\endgroup$ – Christopher Monsanto Apr 28 '11 at 21:07
  • $\begingroup$ @fahrenheit: Great comment! Here's the source: en.wikipedia.org/wiki/George_Dantzig#Mathematical_statistics. $\endgroup$ – M.S. Dousti Apr 29 '11 at 15:47
6
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ hours??? I had problems which I tried to solve for YEARS! $\endgroup$ – trg787 Apr 25 '11 at 0:14
  • 5
    $\begingroup$ And never solved them, of course. $\endgroup$ – trg787 Apr 25 '11 at 0:18
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is exactly what I've done in these situations: obsess until I find an answer, then give strong hints to make the problem doable for undergrads. $\endgroup$ – Fixee Apr 24 '11 at 3:00
4
$\begingroup$

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.

Improve this answer
$\endgroup$

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.