CSE310 Midterm 2 Review This is a study aid to help you to review the materials covered after the first midterm exam The materials 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 Queues Although we have concentrated on max heap in the class you should know both max heap and min 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 also know 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 minheap 6 Know the heapsort algorithm Given an array of unsorted elements show the array structure after the 4 largest elements are sorted 7 2 Medians and Order Statistics We have studied the algorithms for finding the minimum or the maximum We have also studied the linear time selection algorithm 1 1 In class we have studied the median of medians algorithm using group size 5 What happens if 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 recurrence formula to the worst case running time of the corresponding algorithm 3 Disjoint Sets We have studied union by rank and find with path compression You need to know the algorithms for union find set link etc You also need to know the worst case time complexities of these operations 1 If you are given the array structure for the disjoint sets and a particular operation you should be 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 path compression 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 path compression what is the worst case time complexity for a total of m operations 4 Binary Search Trees and Red Black Trees 1 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 same for in order traversal and post order traversal 3 Given a binary search tree and a query Show the element wise comparisons made during the search 4 In a search of a binary search tree can we visit the following elements in the given order 5 10 2 3 4 5 In a search of a binary search tree can we visit the following elements in the given order 2 3 4 5 10 2 6 Given a binary search tree show the resulting binary search tree after the insertion of a new element 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 that there 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 trees 3
View Full Document
Unlocking...