HW1. Introduction (10.09, 23:59)
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 on 6th of September).
EX2. Generate random data consisting of 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) = 4n3 + 0.5n and g(n) = n3. 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) How do you calculate all possible permutations? E.g. create all ways to go through n cities (e.g. in the traveling salesman problem). Or make an inefficient randomised sorting algorithm that permutes the input and tests if it is sorted ... repeating until one of random permutations is. 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/