HW3. Master theorem and Linear Sorting (Monday, 25th of Sep, 23.59)
EX1.(1p) Derive solutions to the following recurrences in two ways: via a recursion tree and via Master Theorem. A solution should include the tightest upper and lower bounds that the recurrence will allow. Assume T(1) ∈ Θ(1)
- T(n) = 2 T(n/2) + O({$ \sqrt{n} $})
- T(n) = 8 T(n/4) + O({$ n \sqrt{n} $})
- T(n) = T(n/3) + T(n/4) + Θ(n) assuming T(a) < T(b) for all a < b
EX2.(1p) Sometimes the recurrent function is not so simple. Consider function T(n) = T(n/2) + n(sin(n - pi/2) + 2), pi = 3.141592…. (sin(x) takes radians as input).
Can the Master theorem be applied here? If not, then why?
Try to plot the function and try to provide some upper and lower bounds for its asymptotic complexity, feel free to use any of the methods available for you (e.g. plotting, proofs, ...).
EX3.(1p) Implement and measure some linear-time sorting algorithm for 8, 32, and 64-bit unsigned (pseudo-)randomly generated integers (e.g. integers from [0,.. 2**32-1]), compare your implementation to the built-in sort times. Describe briefly the selected algorithm. Try to plot all 6 series of numbers (execution times for 8, 32 and 64-bit integers for both your and built-in sort) on one plot. Provide some constant factors by how much the speed differs roughly and comment on the result.
If you were not able to work with 64-bit unsigned integers, briefly describe why.
EX4 and EX5(1p + 1p) In this task, you have the freedom to choose any method and tricks possible and try to work out as fast a sorting algorithm as possible. Try to beat your built-in sorting algorithm. You are also given the freedom of choice over the data you are sorting.
Compare your implementation to some of your previously implemented sorting algorithms (for example in previous homeworks tasks and Ex3 algorithms) and to the built-in sort. Try to describe, where your implementation is good and where it falls off.
Also, don’t worry if you don’t end up beating the built-in algorithm, we appreciate the effort (but try out different things, the task is worth 2 points anyways!)!
Possible things to try (you can try more stuff!):
- Design your own data distribution and dataset. E.g. limit to some max integer size (choose a data type), choose dataset sizes, choose sampling distribution,
- Optimize your implementations of sorting algorithms (e.g. choose better constants for radix sort, number of buckets for bucket sort, …);
- Implement adaptiveness and clever checking to your algorithm, e.g. try to find long sequences of already-sorted data (reversed data) and make use of that knowledge;
- Feel free to compile your code, use threading, multi-processing, extra memory, ...
EX6. Bonus(2p)
Merge sort does not work 'in place' within the original space limits. The simple method uses double the memory by copying values to the helper table and back. There are some rather complicated constant memory overhead schemes to convert merge sort to work in-place, while still ensuring O(n log(n) ) worst-case (google). Your task is to experiment in practice with some simple, possibly non-optimal solution. Modify merge-sort to work in-place, possibly doing more the O(n) work for one merge operation. Measure the actual time on randomly generated data compared to more standard merge sort. Now try to break your own code by generating “worst possible” instances of data.
EX7. Bonus(2p)
Sanos is a supervillain on an intergalactic quest in search of an ancient and powerful artifact called the Thoul Stone. Unfortunately, she has no idea what planet the stone is on. The universe is composed of an infinite number of planets, each identified by a unique positive integer. On each planet is an oracle who, after some persuasion, will tell Sanos whether or not the Thoul Stone is on a planet having a strictly higher planet identifier than their own. Interviewing every oracle in the universe would take forever, and Sanos wants to find the Thoul Stone quickly. Supposing the Thoul Stone resides on planet k describe an algorithm to help Sanos find the Thoul Stone by interviewing at most O(log k) oracles