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.