CS6033 Homework Assignment 4∗
Due February 23rd at 11:59 p.m.
Turn in this assignment on Gradescope as directed by the course assistants No late assignments accepted
1. Insert, in order, the elements 2,19,15,3,42,11,9,18,12,5 into a 2−3−4 tree.
Convert the 2 − 3 − 4 tree you constructed into a red-black binary search tree. In- dicate the color of each node by using letters B (black) and R (red). You may omit representing the NIL nodes.
2. Insert in order the keys 2, 19, 15, 3, 42, 11, 9, 18, 12, 5 into a red-black BST tree. Show your tree after every insertion. Indicate the color of each node by letters B (black) and R (red). You may omit representing the NIL nodes.
After that, convert the red-black BST you have constructed into a 2 − 3 − 4 tree, using the steps we discussed in class.
3. (5 points) What is the minimum and maximum height of a 2 − 3 − 4 tree of n nodes. Justify your answer.
4. Show that the longest simple path from a node x in a red-black tree to a descendant leaf has a length at most twice that of the shortest simple path from x to a descendant leaf.
5. From CLRS 4th edition, page 346, question 13.3-4 (This is equivalent to CLRS 3rd edition page 322, question 13.3-4)
∗Some of these questions came from outside sources. In your psudocode, you may use any function (without writing the code for that function) from CLRS if we discussed that topic in class.
6. When inserting a node into a red-black tree there might occur a red-red violation. Show how each of the cases (i.e. case 1, case 2, and case 3) to solve the red-red violation can be understood by showing how it would be solved in a 2 − 3 − 4 tree (aka 2 − 4 tree)
7. Suppose your neighbor, sweet Mrs. McGregor, has invited you to her house to help her with a computer problem. She has a huge collection of JPEG images of bunny rabbits stored on her computer and a shoebox full of 1 gigabyte USB drives. She is asking that you help her copy her images onto the drives in a way that minimizes the number of drives used. It is easy to determine the size of each image, but finding the optimal way of storing images on the fewest number of drives is an instance of the bin packing problem, which is a difficult problem to solve in general. Nevertheless, Mrs. McGregor has suggested that you use the first fit heuristic to solve this problem, which she recalls from her days as a young computer scientist. In applying this heuristic here, you would consider the images one at a time and, for each image, I, you would store it on the first USB drive where it would fit, considering the drives in order by their remaining storage capacity. Unfortunately, Mrs. McGregor’s way of doing this results in an algorithm with a running time of O(mn), where m is the number of images and n < m is the number of USB drives. Describe how to implement the first fit algorithm here in O(m log n) time instead.
Provide the pseudocode for your implementation.
Question from Goodrich, Michael T.; Tamassia, Roberto. Algorithm Design and Applications
8. Imagine that you work for a database company, which has a popular system for maintaining sorted sets. After a negative review in an influential technology website, the company has decided it needs to convert all of its indexing software from using sorted arrays to an indexing strategy based on using binary search trees, so as to be able to support insertions and deletions more efficiently. Your job is to write a program that can take a sorted array, A, of n elements, and construct a binary search tree, T, storing these same elements, so that doing a binary search for any element in T will run in O(log n) time. Describe an O(n)-time algorithm for doing this conversion.
Question from: Goodrich, Michael T.; Tamassia, Roberto. Algorithm Design and Applications
9. The party at the Chancellor’s house is about to start.
The party is a time for fun, but it could also spell calamity if the Chancellor has too much space juice and forgets a name, or mistakes a person’s planet for the tabloid featured planet, Kardashian. That person may decide “This means war!”
To prevent the outbreak of war, design a system1 to help the Chancellor navigate the treacherous waters of small talk.
Your system will perform the following:
• Insert a new name (and the person’s home planet, alliances, favorite color and kompromat) to the guest list in worst case time O(log n) where n is the size of the guest list
• Return the home planet, alliances, favorite color, and kompromat of a person when provided the person’s name in O(log n) worst case time
• Delete2 a name from the guest list in worst case time O(log n)
• When given a letter of the alphabet, return all the names in the guest list starting3 with that letter in worst case time O(g + log n), where g is the number of people whose name fits the search criteria.
10. The federation is running out of money4. In an effort to increase revenue, the federa- tion has decided to put toll booths on the edges of black holes; the toll will be based on the spaceship weight.(Brilliant right!)
The toll booths (aka black hole locations) have been numbered h1, h2, . . . , hn accord- ing to how close they are to federation headquarters5 where ties are broken arbitrarily.
Design a data structure and implement methods that can perform the following:
(a) insert(d,r) Inserts a new toll booth which has a toll rate of r per ton in O(log n) worst case time. The new toll booth is at distance d from the federation headquarters.
(b) delete(k) Deletes the kth toll booth in O(log n) worst case time. (You are not asked to write this code.)
(c) toll(i, j) Returns the average toll for booths i through j inclusive in O(log n+ #toll booths in i through j) worst case time.
Justify the running times of your methods.
11. (3 bonus points) Think of a good6 exam question for the material covered in Lecture 4.
1Here, we expect a description of the data structure and the pseudocode
2Life is so unfair, alliances shift and someone gets uninvited.
3Even if the Chancellor cannot remember a person’s name, the Chancellor always seems to remember
the first letter of a person’s name.
4You can’t be blamed, anyone would have thought the blinking light at the Chancellor’s party was the
juke box. Its too bad the nuclear warhead you launched took out a nearby planet and nearly bankrupted the entire federation who had to pay reparations.
5i.e. It is important to know which are closest when needing funds to be sent quickly. 6Only well thought out questions will receive the bonus points.
