For this problem you may assume P\ne NP and NP\ne coNP. For each of the following
sets say if it is (1) REG, (2) In P but NOT REG, (3) in NP by not P, (4) Decidable but not in NP,
(5) c.e. but not decidable, or (6) Not c.e.
No explanation needed; however, you get +4 if its right and -2 if you give an answer and its wrong.
You get 0 for a blank. (Hint- DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)
- { G : G is 2-colorable}
- { G : G has an ind set of size 12}
- { a^nb^ma^{n+m} : n,m\in N }
- { (G,rho) : rho IS a proper 3-coloring of G}
- { a^{n^2} : n is not a square }
- A reader once inquired of Marilyn Vos Savant my teacher said we would be penalized for guessing. How will our teacher know that we guessed?
- The above is funny but its a real issue- I really want to give -2 if they GUESSED but give 0 if they honestly thought (say) that a problem was REG when it was P but not REG. Alas we cannot put electrodes into their brains to tell.
- It was a good question in that how well they did on it did correlate pretty well to how they did on the rest of the course and on the rest of the exam.
- Problem 4 most people got wrong-- they thought it was NP but not P. One of the best students in the class who got it wrong said that just SEEING the phrase ``3-col'' and not having had a choice that was NP but not P made him just leap to the NP but not P choice.
- Some students complained to me that having them ALL be ``P but not REG'' was unfair. When I asked him why he told me that since he had 3 of them as ``P but not REG'' his guesses for the rest were NOT that. I reminded him that I didn't just say DO NOT GUESS, I also put LOTS of exclamation points after it.
- (This point was blogged about before here.) I annouced that if a student gets a negative score on the problem I'll give a 0. Drawback- if they are clueless they SHOULD guess one question.
SO what do you think- is it a fair question? Is it a good question?
We usually let a subset of graphs be specified without mentioning the input encoding because all reasonable encodings will be interchangeable in PTIME. However for some graph decision problems, regularity could be affected by the choice of encoding. Indeed you could do this in an artificial way for decision problems in PTIME.
ReplyDeleteGiven the grading rules, if they are clueless they should guess ALL the question (same worst case outcome than guessing one, but better average-case outcome, and higher probability of doing better than zero)
ReplyDeleteIf you want to try to prevent guessing, why not ask for a two or three sentence justification for their answer?
ReplyDeleteMy format for questions like this is true-false, with five points for the correct boolean and up to five for a justification. (The first two of the justification points are pretty easy to get.)
ReplyDeleteI like your questions in the format you gave, but asking them to prove that 1, 2, 4, and 5 are not regular would be a bit messy since they might have to specify the input encoding.
To address Luca's point you should place the floor differently. Give six points for a correct answer, two for saying "pass", and none for a wrong answer.
I see a lot of exam questions like that as a TA, those are fair and acceptable difficulty for an undergrad class.
ReplyDeleteHowever after several semesters of experience I don't ever want to put any T/F, multiple choice, etc on an exam again. They may be easy to grade but inevitably seem to frustrate students who always seem to find creative ways to interpret the question.
I think an alternative approach might be to require explanation, but take off 1 point for every 5 words past the first 10. So an answer like "Apply the pumping lemma, and in PTIME count n,m" is easy to grade but the grader doesn't need to actually read any long-winded answers that (most likely) are guesses anyway.
In our department we do not allow multiple choice questions, on principle. Although grading is a significant problem, there is something inherently not right in having an exam that is structured to make our (the lecturer's) life easy. The students need to work hard answering the questions; we should at least check them (or pay a TA to do it for us). I also think that understanding WHY something is correct, and being able to prove it/justify it is more important than just knowing the right answer. This is not checked in a multiple choice exam.
ReplyDelete1) T/F I really don't like since its just two choices.
ReplyDelete2) Multiple choice with no explanation (which is what I asked) can be good to test intuitions without requiring proof. For example, they should really know that all of the sets in my question were not regular, but it might be hard or odd to prove it. And the
`give a short explanation' always leads to problems with `how short'.
3) The question in question was only 20 points of the exam- Yehuda- would that be against policy? I DO agree that the exam should not be much more than that much multiple choice, maybe 25 points at most.
4) I have mosttly not had the problem of students misunderstanding the question in creative ways. Note that the sets above are very well defined. BUT I do admit that some may have misread the (G,pho) question.
I don't know what policy would officially say, but I am pretty sure that only 20 points of the exam on that sort of question is fine. My objection (and the policy) is regarding a fully multiple choice exam.
ReplyDeleteSo this is no longer that in your "department we do not allow multiple choice questions, on principle" but rather a policy about which you don't know the details and might just be a policy that says you can't give a "fully multiple choice exam" or maybe a policy that came into play after such an exam. Is there actually a policy or is there just a legend of an exam that was all multiple-choice questions that a professor gave that everyone talks about as a bad thing?
DeleteAn interesting variant to this type of question would be to ask students to rank/order these languages in regards to relative complexity (stating equivalencies when necessary under certain reductions). These languages don't even need to be in a complexity class they have seen before. The goal would be to just test their intuition in identifying which problems are hard and which ones are easy.
ReplyDeleteStudents are going to encounter problems that are within rather intricate and obscure complexity classes (e.g. psuedo poly-unicorn time-space). They need to know that there are more complexity classes beyond P, NP, REG, PSPACE, R, RE, etc. They don't need to know what the actual classes are nor do they need to understand proofs classifying their complexity. The ability to guesstimate is pretty key and likely far more useful when moving onwards.