HW1. Introduction (09.09, 23:59)
Reporting is important, let's practice to make your homework attractive:
If you are using Python make sure to complete this homework in the Jupyter Notebook which later lets you produce either HTML or PDF file as a report (and submit the notebook .ipynb itself as the code). If you are not familiar with Jupyter Notebooks follow the instructions for setup and usage from here.
If you use some other programming language please use this Overleaf template (in LaTex) to produce PDF report for this homework and submit your code as usual. You can use a desktop LaTex editor like TeXmaker or come up with your own template similar to the one provided.
EX1. Familiarise yourself with the course and do all the necessary administrative things. Read all the materials in the courses page, definitely:
Also make sure you are registered to Piazza (if you are not then you lose points for this task, the invitation emails will be sent shortly after the first lectures). In order to confirm that you are registered to Piazza, add a comment to the post created by instructors with a link to some useful algorithmics related material, briefly explain the contents of this link in the comment. Please, copy paste a screenshot of your comment to the homework report.
EX2. Randomly generate N integers with values between 0 and maximum integer value, available in the programming language of your choice. Implement any sorting algorithm on your own. Repeat measurements many times (100+) to study how much the sorting times vary (think and explain if you should use the same random integers every time or generate new ones). Increase the array size (N) by several orders of magnitude multiple times and plot the measured sorting times so that you can visually explore the timings. As a result, you should have a plot describing how the sorting time increases when N gets larger. Your answer has to include comments about the experiment setup (what sizes of N did you choose and why, what is the maximum integer in your language, what sorting algorithm you used, how many repetition, etc) and discussion over the results (this will not be stressed explicitly in other tasks, but is expected of you in every answer).
EX3. Now measure the language-specific built-in sorting algorithm. Briefly describe the algorithm and state it’s complexity. Plot the execution times as in EX2, if possible, on the same plot to make comparison easier. Try to also overlay some function f(x) that would approximate the built-in sort timings well. What f(x) did you choose and how?
EX4. Measure how many integers (N) can you roughly sort in 1 minute with both your sort from EX2 and built-in sort from EX3. Predict what would be the sorting times for both algorithms if you increase N 100 times. Do it by extrapolating from the measurements on smaller input sizes and considering the theoretical complexity of the algorithms (or the approximation function, if you don’t know them). Turn the resulting numbers to understandable units (1 day instead of 86400 seconds, etc).
EX5. f(n) = 8n^3 + n and g(n) = n^3. Prove that f(n) = Theta(g(n)) by finding suitable c1, c2 and n0. Plot the function f, and also c1 * g and c2 * g.
EX6. (Bonus 1p) Make an inefficient randomized sorting algorithm that permutes the input and tests if it is sorted. Keep permuting until one of the random permutations is sorted. For how large N it is already infeasible to test all permutations on your laptop? How to create one random permutation of N values (i.e. how to scramble fully the ordered input)? Ps. It's worth to install Gnuplot. Alternatively, there are also web services around it: http://gnuplot.respawned.com/