HW4. Skip-Lists, Trees (26th of September, 23.59)
EX1. Insert 1, 5, 7, 30, 2, 4, 18, 32, 34, 36 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 34. How many comparisons are performed?
EX2. 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? Simulate search for 34. How many comparisons are performed?
EX3. 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 34?
Hint: for simulation, you could either code your own, use online/offline visualisation tool or an actual paper, in either case, make sure your figures are readable and consistent.
EX4. 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. Simulate search for 34. How many comparisons are performed?
EX5. Build a kd-tree on the following 2D data. Split data by choosing median values. Draw the final 2-dimensional kd-tree (You don't have to give every step). You can either do this by hand or write a program to do it for you (or partially do it for you). How would you use this structure to find points in the quadrant [0, 0.5] x [0, 0.5] (bottom-left quadrant).
Hint: Lecture slides.
X Y 0.67, 0.23 0.06, 0.98 0.28, 0.23 0.83, 0.29 0.83, 0.53 0.78, 0.04 0.94, 0.2 0.15, 0.29 0.96, 0.92 0.88, 1.0 0.64, 0.78 0.81, 0.41 0.04, 0.87 0.21, 0.05 0.81, 0.93 0.47, 0.66 0.85, 0.64 0.98, 0.78 0.73, 0.04 0.08, 0.11
EX6. (BONUS, 2p) Implement a Binary Search Tree data structure. You can use either an array-based solution or struct/object-based. Implement at least insert and query functions.
Generate random integers. What is the height of an average random BST? Do this by using generated integers and shuffle them around and make new BST each time. Plot the distribution of tree heights over many random shuffles of data. What can you see? How does the random binary search tree height distribution change as you increase the size of data? Plot it! Can you give a formula to approximate the tree height based on dataset size?
Update/Hint: It is a good idea not to have repeat random numbers in your lists, which are being inserted into your tree. For our experiment, it would add extra noise to measurements. If you did the exercise before this update, it is OK, you can keep repeats!
EX7. (BONUS, 2p) Imagine you are doing some stress-testing on various models of glass cups for a company. Your job is to determine the height from which the glass cups can be dropped and still not break. The setup for your experiment is to have a ladder with n rungs (steps) ad you want to find the highest rung from which you can drop a glass cup and not break it.
- Suppose you are given a budget of k=2 glass cups. Describe a strategy for finding the highest safe rung that requires you to drop a glass cup at most f(n) times, for some function f(n) that grows slower than linearly.
- Describe your strategy for k > 2 glass cups.