HW4. Skip-Lists, Trees (30th of September, 23.59)
EX1. Implement and measure some linear-time sorting algorithm for 8, 32, and 64-bit unsigned integers, compare the speed to 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.
Hint: it might be tricky to get counting sort working with large numbers, so maybe consider some other sorting algorithm or think of a way around the problem.
EX2. Insert 2, 6, 8, 31, 3, 5, 19, 33, 35, 37 into skip-list by simulating the process "on paper". Use a fair (actual) coin to provide the "depth" for each node. Show the skip-list after every insertion and the final list. Comment on how the element is added to the list (thoroughly with at least one insertion, mentioning exact operations, e.g. what comparisons are made while adding, etc). Next, simulate search for 36. How many comparisons performed?
Hint: for simulation, you can use either some (online/offline) visualisation tool or an actual paper, in either case, make sure your figures are readable and consistent.
EX3. Insert the same values into a binary search tree in the same manner. Describe how the insertion is done and show at least a few intermediate steps in addition to the final tree. How skewed is the tree?
EX4. Now perform the same, but perform the AVL balancing. Show the tree before and after each balancing and mention how do you decide that the tree has to be balanced. How many rotations did you perform? Show the final tree. How many comparisons to search for 36?
EX5. Now perform again the BST insertion, but follow red-black re-balancing on the way. Again, show the tree before and after every balancing and mention how do you decide that balancing needs to be done and how do you decide which case of balancing it is. How many rotations did you perform? Show the final tree.
EX6. (Bonus 2p) Try solving the "Minutesort" benchmark from sortbenchmark.org, using their 100 byte records, of which first 10 bytes are key; as generated by gensort. If you did not manage to generate records with gensort, you can generate similar data yourself, but get only 1 point for this exercise. Which year you might have won the competition using merely a modern laptop? Try some of the most straightforward approaches only - you have only limited time. How much slower is this sort as compared to EX 1 linear time effort for the same nr. of records.