HW4. Skip-Lists, Trees (2nd of October, 23.59)
EX1. (1p) 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?
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.
EX2. (1p) 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. (1p) 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?
EX4 (1p). 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?
EX5. (1p) 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, 1p + 1p)
- Given an array of items A = (a0, . . . , an-1), describe a O(n)-time algorithm to construct a binary tree T containing the items in A such that (i) the item stored in the ith node of T’s traversal order is item ai, and (ii) T has height O(log n).
- Below is a Sequence AVL Tree T. Perform operation T.delete_(8) and draw the tree after each rotation operation performed during the operation. In Sequence AVL, we augment each node, with the size of its subtree. Thus the node’s size will computed in O(1), given the sizes of its children by summing them and adding 1.
Hint: Use online/offline visualisation tool or an actual paper.