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

21–30 of 35 posts

Re: Should CS students be graded on performance?

#21

Post by chalst »

JoachimSchipper wrote: post #18
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.

But this optimisation is applied many times: it is the leaf case of such qsort algorithms. So it affects the constant scaling factor at all ns, not just for small ns.

Re: Should CS students be graded on performance?

#23

Post by DarkShikari »

The ACM contest has it right: specify the size of the input and the running time available. The program must be able to run an input up to that size in the given runtime. That's it: no more, no less.

At Harvey Mudd College, we have a class based on the ACM which works similarly, though with relaxed runtime constraints: 42 minutes per problem. In practice, you rarely need more than a few seconds, but the 42 minute cutoff (combined with large problem sizes) is a great way to prevent people from using brute-force approaches when there's a smarter option available.

Re: Should CS students be graded on performance?

#24

Post by mvanveen »

YES. My Data Structures and Algorithms class was graded by benchmark (ECS 60, Sean Davis, UC Davis). Being graded this way was one of the most valuable collegiate experiences I've had (I'm a fourth year on the way out).

Sean gives his students two "challenge programs" a quarter. The first program is usually ultimately a matter of picking/optimizing the right data structure. We do graph algorithms by the 2nd half and so the later challenge problem is inevitably some graph algorithm.

The challenges are close to real world problems. For ex., our 2nd challenge program was to determine the maximum # of donations Obama could receive at any one time given a capacitance graph of his website's network topology (I took the class around the '08 election). We had to design, implement, and test everything by ourselves.

I don't agree with the naysayers who suggest that grading this way doesn't teach the really important software engineering tasks. You really had to feel out the problem domain in order to get the best optimization, and it the book answer wasn't always the best answer. Optimization is about a lot more than simply picking the right data structure or algorithm.

Partnering with the crazy russian genius with an 8086 instruction set in his head that quarter made me the C programmer I am today.

TL;DR Grading by benchmark makes students better programmers.

Re: Should CS students be graded on performance?

#25

Post by Someone »

seancron wrote: post #5
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?

Could you explain what you mean a bit more by big O notation not telling the whole truth? Are you referring to the fact that algorithms that look the same in big O notation might have drastically different constants, which can affect real-world performance?

It can be worse. A O(n log n) algorithm might be slower than a O(n^2) algorithm for all practical values of n.

Also, one should be careful what to count. Sorting strings, for example, is not quite O(n log n); average string length/expected offset of first difference/whatever should also be in that O().

Along the same line, for many algorithms, cache-locality is more important than number of CPU cycles. So, counting cache misses rather tha cycles can be the better way to judge an algorithm.

Re: Should CS students be graded on performance?

#26

Post by JoachimSchipper »

DarkShikari wrote: post #23

The ACM contest has it right: specify the size of the input and the running time available. The program must be able to run an input up to that size in the given runtime. That's it: no more, no less. At Harvey Mudd College, we have a class based on the ACM which works similarly, though with relaxed runtime constraints: 42 minutes per problem. In practice, you rarely need more than a few seconds, but the 42 minute cut…

42 minutes? I recall more than one ACM problem that could be bruteforced just within the running time (in C). Actually, I did really badly in one contest because I applied serious mathematics to one such problem (which gave a much faster program, but writing it took a lot of time and fast enough is fast enough.)

Re: Should CS students be graded on performance?

#27

Post by DarkShikari »

JoachimSchipper wrote: post #26
DarkShikari wrote: post #23

The ACM contest has it right: specify the size of the input and the running time available. The program must be able to run an input up to that size in the given runtime. That's it: no more, no less. At Harvey Mudd College, we have a class based on the ACM which works similarly, though with relaxed runtime constraints: 42 minutes per problem. In practice, you rarely need more than a few seconds, but the 42 minute cut…

42 minutes? I recall more than one ACM problem that could be bruteforced just within the running time (in C). Actually, I did really badly in one contest because I applied serious mathematics to one such problem (which gave a much faster program, but writing it took a lot of time and fast enough is fast enough.)

Sure, some can be bruteforced, but typically it's intentional.

A good example of what I mentioned was an assignment this week. Last week, the input size was constrained to a thousand or so, and Floyd-Warshall was able to solve the problem. This week, it's the same problem, but with inputs up to ~50,000 in size. The old program, run on the new test cases, doesn't finish in a day.

Re: Should CS students be graded on performance?

#28

Post by thwarted »

baddox wrote: post #16
moxiemk1 wrote: post #6

Earlier quoted context omitted.

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…

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.

𝜪 is an indicator of work (number of steps) for a given n, not wall-clock time. This gets mildly confusing when you give each unit of work a value of 1 unit of time, and then talk about it in terms of time-like labels (seconds, hours, age of the universe).

I don't see that there's value is comparing an algorithm of n = "some input size" to another one with a different 𝜪 of n = 10. When comparing, you don't care about the value of n, you only care about how n changes the amount of work. When actually selecting and implementing, you care about n (because n will often be limited by something else, say available memory) -- if your n is small and pragmatically you know that even a terrible, brute-force algorithm will finish in a second, you use the one that is easier to implement and put an implementation specific limit on n (and you also put a TODO or FIXME on it with a comment that says if n ever needs to be increased, a different algorithm should be used).

Re: Should CS students be graded on performance?

#29

Post by glenjamin »

moe wrote: post #10
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…

First, find a better color scheme for something you intend people to read. That was painful. http://rdd.me/3ltgecrd

On my iPhone safari, readability killed all the big Os, makes the article very hard to follow.

Re: Should CS students be graded on performance?

#30

Post by JoachimSchipper »

chalst wrote: post #21
JoachimSchipper wrote: post #18

Earlier quoted context omitted.

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.

But this optimisation is applied many times: it is the leaf case of such qsort algorithms. So it affects the constant scaling factor at all n s, not just for small n s.

I thought I was being totally clear, but seeing your comment and its upvotes, apparently not. What exactly did your "but" refer to? I think we're in complete agreement...

(I was trying to say: here's an example where properly using a fast-for-few-elements "toy" algorithm can improve real-world performance on a "serious" problem like sorting a big chunk of data. So big-O is not everything.)

Post reply on HN