News for hackers. Stuff that matters.
Re:Should CS students be graded on performance? by DarkShikari on Sunday March 06, 2011 @03:07AM (#2293765)
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? by JoachimSchipper on Sunday March 06, 2011 @03:37AM (#2293807)
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? by DarkShikari on Sunday March 06, 2011 @03:45AM (#2293820)
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.