CSE310 Midterm 2 ReviewThis is a study aid to help you to review the materials covered after the first midterm exam. Thematerials we have covered include the following• Heaps and Priority Queues (Chapter 6)• Medians and Order Statistics (Chapter 9)• Disjoint Sets (Chapter 21)• Binary Search Trees and Red Black Trees (Chapters 12 and 13.1)1 Heaps and Priority QueuesAlthough we have concentrated on max-heap in the class, you should know both max-heap andmin-heap operations. The following are some problems to help you review the materials.1. Is an array that is in sorted order a min-heap?2. Given an array, check whether it is a max-heap.3. Given an array, apply the buildheap algorithm to turn it into a max-heap. You should alsoknow the min-heap version of this problem.4. Know the insert operation for both max-heap and min-heap.5. Know the increase key operation for max-heap and the decrease key operation for min-heap.6. Know the heapsort algorithm. Given an array of unsorted elements, show the array structureafter the 4 largest elements are sorted.7.2 Medians and Order StatisticsWe have studied the algorithms for finding the minimum or the maximum. We have also studiedthe linear-time selection algorithm.11. In class, we have studied the median-of-medians algorithm using group size 5. What happensif we use group size 4? What happens if we use group size 17?2. Suppose we design the median-of-medians algorithm using group size 13, derive the recurrenceformula to the worst-case running time of the corresponding algorithm.3 Disjoint SetsWe have studied union by rank and find with path compression. You need to know the algo-rithms for union, find-set, link, etc. You also need to know the worst-case time complexities ofthese operations.1. If you are given the array structure for the disjoint sets, and a particular operation, you shouldbe able to write out the resulting array structure after the operation.2. Assume that there are n elements. If you are using union by rank and find without pathcompression, what is the worst-case time complexity for a total of m operations?3. Assume that there are n elements. If you are using union by rank and find with pathcompression, what is the worst-case time complexity for a total of m operations?4 Binary Search Trees and Red Black Trees1. For the set of {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of heights 2, 3, 4, 5, and 6.2. Given a binary search tree, perform pre-order traversal. You should be able to do that samefor in-order traversal and post-order traversal.3. Given a binary search tree and a query. Show the element-wise comparisons made during thesearch.4. In a search of a binary search tree, can we visit the following elements in the given order?5, 10, 2, 3, 45. In a search of a binary search tree, can we visit the following elements in the given order?2, 3, 4, 5, 1026. Given a binary search tree, show the resulting binary search tree after the insertion of a newelement.7. Given a binary search tree, show the resulting binary search tree after the deletion of a node.8. What is the worst-case time complexities for insertion, deletion, search? Assuming thatthere are n elements in the binary search tree.9. Answer the above questions when the binary search tree is a red-black tree.10. What are the five properties of a red-black tree (in the given order).11. Which property (properties) may be violated by an insertion operation?12. Which property (properties) may be violated by a deletion operation?13. What are the advantages of red-black trees over binary search
View Full Document
Unlocking...