solipsist comments on Exams and Overfitting - Less Wrong

12 Post author: robot-dreams 06 January 2015 07:35PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (47)

Comments (47)

You are viewing a single comment's thread. Show more comments above.

Comment author: IlyaShpitser 06 January 2015 11:27:53PM *  8 points [-]

Manuel Blum generally has one open* problem on his exams. Manuel Blum was one of the best teachers I ever had (he taught complexity theory at Berkeley -- he's at CMU now). It is possible to get 1000 out of 100 on his exams, apparently.

  • In the sense of "no one bothered writing it up, but generally you should be able to do it in a timed setting if you thought about a class problem in depth as is encouraged but not required."

Consider that if a somewhat "out of the left field" problem is on the exam, it is there to separate the upper end of the curve. One could imagine some reasons a professor might want to do that.

Comment author: solipsist 07 January 2015 02:54:43AM 14 points [-]

"Write a polynomial-time algorithm for X, or prove X is NP-Complete. For extra credit, do both."

Comment author: roystgnr 08 January 2015 04:14:41PM *  3 points [-]

"Hmm... I can prove that this is in NP, but not in P or in NP-Complete. That's not worth any points at all!" (crumples up and throws away paper)

Comment author: asr 08 January 2015 10:16:37PM *  1 point [-]

Speaking as a former algorithms-and-complexity TA --

Proving something is in NP is usually trivial, but probably would be worth a point or two. The people taking complexity at a top-tier school have generally mastered the art of partial credit and know to write down anything plausibly relevant that occurs to them.

Comment author: solipsist 09 January 2015 12:32:08AM *  7 points [-]

I think roystgnr's comment was meant to be parsed as:

"Hmm... I can prove that this is in NP, and I can prove it is not in P and is not in NP-Complete. But that's not worth any points at all!" (crumples up and throws away paper)

Corollary:

...they shouldn't have crumpled that piece of paper.

Comment author: roystgnr 12 January 2015 03:37:29PM 1 point [-]

That was my intention; thanks for fixing the phrasing.

Powered by Reddit Powered by Reddit