1
$\begingroup$

In my course we discuss algorithms (greedy, dp, div & conquer, etc.) and efficiency. Do you have any experience with assignments that consider also time of execution as a criterion for grading? Do you use any tools for measuring execution time?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Execution time is unreliable due to variations in hardware and, especially, operating systems. Paging and multi-level cache can make such things worthless. That is why theoretical measures are used.

The actual execution time depends on the specific implementation of the algorithm, not its structure. Implemented poorly in Java it will run slower than if implemented well in C (and conversely). Paged operating systems, such as Unix and its variants (and others) put an extra load on algorithms at scale. Multi level cache can speed things up but vary between processors.

Efficiency of an algorithm is a theoretical concept and so is measured theoretically, perhaps by counting comparisons. This might mean something if you compare two algorithms on the same hardware, but may even be misleading if the implementation causes, for example, page thrashing.

In addition, most modern OSs are multiprogrammed and a given program has little control over whether it has complete control over the processor while it executes, or even over a single thread.

But most operating systems will have a way to give you the actual running time of the execution of a program. A few thousand executions will give you an accurate picture for that algorithm on that set of inputs, but might vary widely if you double the inputs.

See the Linux date command for example. You can integrate it into a shell script that executes a program a few thousand times and get some averages.

$\endgroup$
3
  • $\begingroup$ you are making valid and good points. I was wondering, how do they compare timing in competitive programming then? $\endgroup$ Jan 5, 2021 at 19:07
  • 1
    $\begingroup$ For complete programs, not algorithms, a crude measure such as the difference between two unix times (in seconds) is probably enough. But algorithms are intended to be rather dense instruction sequences. $\endgroup$
    – Buffy
    Jan 5, 2021 at 19:15
  • $\begingroup$ @DrimadesBoy, I served as judge on ICPC once. Programming contests force to code one algorithm for a problem. As far as they allow several languages, each problem has a different timeout (rather generously assigned) for each language (to weed out brute-force style solutions and infinite loops).To me they look based on rough speed comparisons bewteen languages (e.g C/C++ 10 times faster than Java). There are several on-line judges around, check their time allowments for problems, $\endgroup$
    – vonbrand
    May 9, 2021 at 23:34
2
$\begingroup$

To build on what @Buffy said, one way you could go about it in a language like Java is to make them use your own custom data-wrapping objects. If the algorithm takes ints, pass in Ents instead. If your algorithm takes doubles, use Dobles -- the name doesn't matter.

The reason to do this is that you can implement Comparable and override equals(...) in order to keep track of accurate counts of all comparisons with static variables. Then you can use reasonable ranges to figure out the run-time of the operation, regardless of the system clock, threading, or the hilarious cat videos running on your computer while you are grading labs.

You'd have to explain to the students what you are doing, and mention that extracting the data and simply using it directly for the comparisons would be considered a cheat, and that anyone engaging in such actions would have automatic zeros on the assignment.

If I took this route, I would also provide direct sample code that simply demonstrates how to mimic ==, <, <=, >, and >= functionality with the provided data types. I would not consider figuring out how to use my wrappers something that the students should need to do. The wrappers would be in place purely for the purposes of accurate grading. They shouldn't, themselves, be part of the puzzle of the assignment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.