You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

IlyaShpitser comments on Exams and Overfitting - Less Wrong Discussion

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.

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