Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>See the <a href="https://www.devopsrun.com/t-how-to-get-current-unix-timestamp-or-epoch-time-from-a-linux-command-line" rel="nofollow noreferrer">Linux date command</a> for example. You can integrate it into a shell script that executes a program a few thousand times and get some averages.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T19:07:45.647Z
Answers.Text: you are making valid and good points. I was wondering, how do they compare timing in competitive programming then?
Answers.UserDisplayName: Drimades Boy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T19:15:37.850Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-09T23:34:45.823Z
Answers.Text: @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,
Answers.UserDisplayName: vonbrand
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T18:44:29.710Z
Answers.LastActivityDate: 2021-01-05T18:55:14.177Z
Answers.LastEditDate: 2021-01-05T18:55:14.177Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>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 <code>int</code>s, pass in <code>Ent</code>s instead.  If your algorithm takes doubles, use <code>Dobles</code> -- the name doesn't matter.</p>
  <p>The reason to do this is that you can implement <code>Comparable</code> and override <code>equals(...)</code> 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.</p>
  <p>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.</p>
  <p>If I took this route, I would also provide direct sample code that simply demonstrates how to mimic <code>==</code>, <code>&lt;</code>, <code>&lt;=</code>, <code>&gt;</code>, and <code>&gt;=</code> functionality with the provided data types.  I would not consider figuring out <em>how</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T19:58:01.083Z
Answers.LastActivityDate: 2021-01-05T19:58:01.083Z
Answers.UserDisplayName: Ben I.
Body: <p>In my course we discuss algorithms (greedy, dp, div &amp; 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?</p>
  
Tags: <algorithms><grading>
Title: Algorithm Design challenges
ThreadText: # Algorithm Design challenges
  
  (Asked by: username_0 on 2021-01-05)
  
  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?
  
  **Tags:** algorithms, grading
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-01-05. Score: 3
  
  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](https://www.devopsrun.com/t-how-to-get-current-unix-timestamp-or-epoch-time-from-a-linux-command-line) for example. You can integrate it into a shell script that executes a program a few thousand times and get some averages.
  
  > **Comments:**
  > **username_0**: you are making valid and good points. I was wondering, how do they compare timing in competitive programming then?  
  > **username_1**: 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.  
  > **username_2**: @username_0, 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,  
  
  ---
  
  ### Answer by username_3 on 2021-01-05. Score: 2
  
  To build on what @username_1 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 `int`s, pass in `Ent`s 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.
  
  
  ---
  
  