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?
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.
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
>= 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.