One of them was: Let L be in DTIME(T(n)). Give an algorithm for L*. Try to make it efficient. What is the time complexity of your algorithm? (I had done that if L is in P then L^* is in P in class earlier in the term.)

My intention was that they do the Dynamic Programming solution. Since it wasn't being collected I didn't have to worry about what would happen if they did it by brute force. When I went over it in class I did the Dynamic Programming Solution, which is roughly T(n)^3 time.

I allow my students to bring in a sheet of notes that they make up themselves.

On the exam was the problem: Let L_1 \in DTIME(T_1(n)) and L_2\in DTIME(T_2(n)).

Give an algorithm for L_1L_2. What is the time complexity of your algorithm?

Of my 20 students 5 of them gave me, word for word, the dynamic programming solution to the L, L* problem.

Why would they do this? Speculations:

- They just copied it off of their cheat sheet with no understanding.
- They wanted pity points (they didn't get any and I told the class that if a similar thing happens on the final I will give them LESS THAN zero on the problem).
- They so hoped that the L, L* problem would be on the exam (possibly becuase it was on their cheat sheet) that they misread the problem.
- They thought `Dr. Gasarch wouldn't have put it on the practice exam unless it was on the real exam' (or something like that), so they misread it.

But I ask-- (1) is this kind of thing common? For my Sophomore Dscrete Math yes, but I was very slightly surprised to see it in my senior course. (2) Do you have examples? I am sure that you do, but my point is NOT to do student-bashing, its to ask WHY they do this.

The "nearest neighbor solution" is definitely one I see, but the "random n-gram solution" is another good one--with even more hilarious results. (nb, I mostly teach graduate students)

ReplyDeleteYes, this is unfortunately common. I call them cargo-cult solutions.

ReplyDeleteMy answer to the "less than zero" urge is to give 25% partial credit on ANY question for writing "I don't know" (and nothing else) and 0 points for solving the wrong problem. And of course I warn the students in advance. But I still get a few cargo-cult solutions on every exam.

Very common. Saw this so many times, even at the graduate level. They don't understand the question and they are just writing the closest thing they heard or which is on the cheat sheet, hoping that they may get extra credit for "something" (and if not, better than writing nothing).

ReplyDeleteAs Jeff Erickson suggests, a different grading policy is very helpful to prevent this. I also highly reward wrong attempts to solve the right problem, if some intellectual effort is clearly visible.

The sentence "(I had done that if P is in P then L^* is in P in class earlier in the term.)" needs some fixing.

ReplyDeleteI gave an exam once where I essentially had shown them four proof techniques and the exam happened to have four questions and one technique was used twice and once wasn't used. Several students tried to use the technique on the last problem, where it made no sense at all. My best guess was they figured it was the only technique "left" so it had to be what I wanted.

ReplyDeleteA friend of mine was taking a math class, and she tried to do the homework via a pattern-matching approach without thinking at all about what the equations meant. The weird part was that it wasn't because she couldn't understand the concepts once explained, or because she didn't want to try, it was as if she thought that's how people did it and that there was no explanation for anything.

ReplyDeleteI don't think that can explain your students, though, as I don't imagine how you'd get to a senior level course thinking that way.