HW3. Master theorem and Linear Sorting (19th of Sep, 23.59)
EX1. Let’s check out the Master theorem. Give an example of a function for each of the three cases of the theorem.
Solve those given recurrences using Master theorem (write down a, b, log_b(a). f(n)), and show how you decided which case the function is. Make sure to check the regularity condition if needed!
Plot your chosen functions, you can write a basic program as done previously, e.g. define a function to calculate T(n) = a T(n/b) + f(n). You can assume again as in the previous week that T(1) is 1.
EX2. 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. 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 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(1p)
The problem was formulated by M. I. Shamos and D. Hoey in the early 1970s, as part to compute efficient algorithms for basic computational primitives in geometry and found its uses into areas of graphics, computer vision, etc.
- Given n points in the 1D plane, find the pair that is closest together in O(nlogn) time.