Add as many "const" or, preferably, "constexpr" keywords as allowed to the wildptr-fixed.cpp code.
The keyword auto allows the programmer to declare/define variables by implicit typing; this is still static typing, since the compiler must be able to identify the type, but nonetheless a deviation to the more traditional and common paradigm of C/C++, which relies on explicit typing.
Take the code const-array.cpp and use auto to replace as many explicit types as allowed. What do you think: Which of these allowed implicit-type declarations would you actually use in programming practice?
Run the buggy random-walk code with a memory leak from the lecture on your system. Figure out for how many steps m you can run the program without it causing major disruptions to your system (due to the system running out of memory), with a chain length chosen as N = 1024.
How do you recognize that the system is running out of memory?
Now let the number of steps m be constant, chosen as described above, but decrease the chain length in powers of two: 1024, 512, …; measure the runtime of the program as a function of N. For example, on a Linux command line, you can use the command time for this purpose; if m = 2000000, you would be running time ./memleak 1024 2000000, then time ./memleak 512 2000000, then time ./memleak 256 2000000, and so on. In-code, this can be done using the chrono library:
#include <chrono>
…
{ … /* somewhere */
auto t0 = std::chrono::high_resolution_clock::now();
… // here the work is being done
auto t1 = std::chrono::high_resolution_clock::now();
auto delta_t = std::chrono::duration_cast<std::chrono::microseconds>(t1-t0).count();
std::cout << "this took " << 0.001*delta_t << " ms to run.\n";
…
}
Plot the runtime t as a function of N.
Next, do the same exercise, but with mN constant; e.g., in the scenario above, you would run time ./memleak 1024 2000000, then time ./memleak 512 4000000, then time ./memleak 256 8000000, and so on. Plot the runtime t as a function of N.
Now, fix the broken code. What approach did you decide to follow? Run it and confirm for yourself that the memory leak is gone. ("For yourself" means: You are not expected to include anything about this in your submission - it just makes sense to do it.)
Repeat the measurement series with constant mN, and determine the speedup. In this and similar cases, the speedup is simply defined as the runtime of the original (worse) version of the code divided by the runtime of the new (improved) version.
(Don't submit the code from this step of the work; instead, submit only the code obtained after carrying out the subsequent step, problem no. 12. From this step, submit only the results on the runtime.)
Beyond the bug with the memory leak, there are other ways in which the code might be improved to become faster. Find and implement some. Submit the code and also a very brief explanation of what you did (bullet point list, or similar). Confirm for yourself that the results of the computation are unaffected by your improvements.
Measure the runtime once again. What speedup with respect to the original version do you obtain?
The "memleak" code, and hopefully your fixed version of it, is a simulation of a toy system. That system can e.g. be interpreted as a ring-like chain of elements, each of which move up and down stochastically (at random), but not independent of each other, since they are attracted to their two neighbours. For each configuration, the code computes the "elongation", i.e., the difference between the highest and the lowest coordinate of any elements of the chain.
In addition to the elongation for the present configuration, the code keeps track of the greatest elongation so far, as well as the average elongation. Analyse the results for the average and extreme (greatest) elongations that you obtained from your simulations with constant mN, as a function of the chain length N. How would you describe that behaviour - is there any generalizable hypothesis that you would formulate based on your results?
Data points in scientific research, just like data points for any use whatsover in the context of reliable systems, are incomplete if they do not come with an error bar, confidence interval, or comparable quantitative reliability metric.
What method have you learnt in your course of studies and/or practical experience to use in a case like this?
Provide an error bar for all your data points on the average elongation. Remember that without an error bar, any such data are useless.
Python lists and C++ STL vectors are similar data structures, dynamic arrays, though naturally their internal technical implementations differ. Use both languages to write a simple code that keeps appending elements of the same type (e.g., a sequence of integers) to a dynamic array. Compare the runtime of both, at least for two different final sizes of the dynamic array.
(submit through Canvas by end of 27th February 2024)