Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Should CS students be graded on performance?

sbcoded.com

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Should CS students be graded on performance?

#11

Post by drfugly »

kd0amg wrote: post #4
drfugly wrote: post #3

Earlier quoted context omitted.

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I understand that for the most part you shouldn't have to worry about it, but shouldn't we still warn students about this?

Do you mean something like the case of quicksort mentioned in the post?[1] I was taught average- and best-case analysis along with worst-case analysis. Or do you mean some other fact not revealed by that analysis? [1] "Quicksort is a magical algorithm that theory tells us runs in O(n^2)"

Right, but there is also the cases where a nlg(n) quicksort for the most part is slower than the O(n^2) version in the real world. I wonder if current CS teaching is completely ignoring real-word performance.

Re: Should CS students be graded on performance?

#12

Post by baddox »

parfe wrote: post #7

First, find a better color scheme for something you intend people to read. That was painful. Second, when I was a CS student I expected to be graded on my response to a particular problem. If you wanted me to roll my own sort, I expect that to be specified. If you want me to explain in comments why I chose certain algorithms say something in class. I'm not going to waste time implementing an efficient sorting algorit…

I tried for a moment to figure out how to deselect all the text.

Re: Should CS students be graded on performance?

#13

Post by baddox »

Generally, performance isn't interesting in cases where asymptotic running time isn't dominant. You could sort 3 items with a couple of `if` statements, which would compile to a handful of microprocessor instructions. That's not interesting. Surely, in any data structure or algorithms course offered as part of a CS degree, the sorting assignments are for the "general sorting" problem. This implies relatively large data sets (and unpredictable, since you don't expect to be able to use a faster non-comparison sorting algorithm).

Re: Should CS students be graded on performance?

#14

Post by anonymoushn »

drfugly wrote: post #3
moxiemk1 wrote: post #2

It depends on the context of the problem: * If it's being framed as being applied to a small number of items on one machine, I'd mark down for premature optimization. Normally such assignments have a specific point, and going off the deep end with efficiency measuring often misses it. * If it's being framed as being applied to huge data sets, asymptotic complexity is the metric to go off of. * If it's being framed as…

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I understand that for the most part you shouldn't have to worry about it, but shouldn't we still warn students about this?

Yes, a few professors discussed situations in which a theoretically slower algorithm was better in almost all real situations, and situations like timsort in which it is best to fall back on an asymptotically slow algorithm when your inputs are very small.

Re: Should CS students be graded on performance?

#15

Post by baddox »

drfugly wrote: post #3
moxiemk1 wrote: post #2

It depends on the context of the problem: * If it's being framed as being applied to a small number of items on one machine, I'd mark down for premature optimization. Normally such assignments have a specific point, and going off the deep end with efficiency measuring often misses it. * If it's being framed as being applied to huge data sets, asymptotic complexity is the metric to go off of. * If it's being framed as…

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I understand that for the most part you shouldn't have to worry about it, but shouldn't we still warn students about this?

We were taught what big O notation actually is, so yes. The whole point of big O notation, what makes it so useful, is that it hides information (namely constant factors). It's not supposed to "tell the whole truth," it's supposed to allow the analysis of algorithms not at any one runtime, but in an asymptotic mindset.

With big O notation, you're not interested in how fast an algorithm ever actually runs (for that is the realm of constant factors), but rather how its running time changes as the size of its input changes.

Re: Should CS students be graded on performance?

#16

Post by baddox »

moxiemk1 wrote: post #6
drfugly wrote: post #3

Earlier quoted context omitted.

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I understand that for the most part you shouldn't have to worry about it, but shouldn't we still warn students about this?

Absolutely! I suppose when I speak of asymptotic analysis, I'm including average case/expected case/degenerate case analysis in the whole exercise. Perhaps "runtime analysis" is a better term - it can then incorporate latency analysis as well. But yes, that was integal to the treatment of the subject. I remember having to determine what the worst-case of quicksort looks like as a part of an assignment to exhibit, in…

We talked about these things as well. I remember studying how to calculate the percentage of data sets of a given size that would bring out the worst-case running time of quick-sort.

Really, I think the issue with all the criticisms of asymptotic analysis is simply that too many people (even brilliant programmers and CS majors) just don't understand what big O notation actually means. If an algorithm is in, say, O(n lg n), that says nothing about how fast it runs with 10 inputs, 1,000 inputs, 1,000,000,000, etc. It merely says how its running time changes as its input size increases. The algorithm could literally take 1,000 years with an input size of 10. That doesn't matter. At some input size, it will run faster than a different algorithm in O(n^2) that completes in 1 millisecond with an input size of 10.

Re: Should CS students be graded on performance?

#17

Post by patio11 »

Aside from teaching big O notation, I would be skeptical of grading for performance. Teaching people that the performance code they write to solve a toy problem matters might lead them to go into industry and then perform microoptimizations on code to solve performance problems when they are virtually universally caused by the interaction of many moving parts.

If you're doing web apps, application code is close to the last place I'd reasonably expect there to be severe performance issues. You're far, far more likely to either blow something architecturally ("We call a foreign API in the request/response cycle.") or flub settings where simple best practices produce repeatable results ("It is 2011 -- do you know where your gzip is?")

Re: Should CS students be graded on performance?

#18

Post by JoachimSchipper »

moxiemk1 wrote: post #2

It depends on the context of the problem: * If it's being framed as being applied to a small number of items on one machine, I'd mark down for premature optimization. Normally such assignments have a specific point, and going off the deep end with efficiency measuring often misses it. * If it's being framed as being applied to huge data sets, asymptotic complexity is the metric to go off of. * If it's being framed as…

Actually, "fast on small n" does matter. Many real-world qsort() implementations have an insertion sort in the inner loop (e.g. for sorting chunks of 8 elements) - and while the number of elements is small, this routine is called often enough that it matters.

That said, some abstraction is useful too.

Re: Should CS students be graded on performance?

#20

Post by tomwans »

drfugly wrote: post #8
parfe wrote: post #7

First, find a better color scheme for something you intend people to read. That was painful. Second, when I was a CS student I expected to be graded on my response to a particular problem. If you wanted me to roll my own sort, I expect that to be specified. If you want me to explain in comments why I chose certain algorithms say something in class. I'm not going to waste time implementing an efficient sorting algorit…

Will do for the color scheme. What I was trying to ask was: Should real world performance be more heavily weighed? I feel like right now all the CS curriculum focuses on is O() performance as the end all.

Normally, my (favorite) CS professor would weigh code clarity more strongly than performance. However, he would sometimes put up assignments that focused almost entirely on the performance, in which he obviously changed the grading weights.
Post reply on HN