CSc 345: Homework Assignment 4 Assigned: Tuesday March 10 2015 Due: 2:00 PM, Tuesday March 31 2015 Clear, neat and concise solutions are required in order to receive full credit so revise your work carefully before submission, and consider how your work is presented. If you cannot solve a particular problem, state this clearly in your write-up, and write down only what you know to be correct. For involved proofs, first outline the argument and the delve into the details. 1. (10 pts) BST Manipulation: (a) Show what a BST looks like after inserting 10, 5, 2, 20, 30, 25, 8, 3, 40, 38, 25, 33, 36, 34, 37 (you can just show the final tree). (b) Show what the BST looks like after deleting 2. (c) Show what the BST looks like after deleting 30. (d) Show what the BST looks like after deleting 33. (e) Show that the BST looks like after inserting 30. 2. (10 pts) (a) Let v be an internal node in a BST with both a left and a right child. Prove that v’s successor does not have a left child. (b) Let T be a binary search tree and let u and v be two arbitrary nodes in T . Let T 0 be the tree which results from deleting u and then deleting v. Let T 00 be the tree which results from deleting v and then deleting u. Prove or disprove that T 0 and T 00 are the same. 3. (10 pts) Design and analyze the algorithm for computing the predecessor of a node in a BST. 4. (10 pts) Let T be a proper binary tree with n nodes and height h. Prove: (a) The number of leaves is in the range [h + 1, 2h ]. (b) The number of internal nodes is in the range [h, 2h − 1]. (c) The height of T is in the range [lg(n + 1) − 1, (n − 1)/2]. 5. (10 pts) Recall that we discussed three ways to visit the nodes in a binary tree: PreOrder, InOrder, PostOrder. (a) Given the result of one of the binary tree visits, is it possible to draw the actual tree? If so, design and analyze an efficient algorithm for it; otherwise show a counterexample. (Hint: this problem has 3 parts.) (b) Given a pair of these tree visits, is it possible to draw the actual tree? If so, design and analyze an efficient algorithm for it; otherwise show a counterexample. (Hint: this problem also has 3 parts.) 6. (10 pts) A sorting algorithm is stable if it preserves the initial order of elements with the same key. A sorting algorithm is in-place if it doesn’t require an additional array for intermediate steps. We have seen several different sorting algorithms. Which of the following are stable and which are in-place: InsertionSort, MergeSort, HeapSort, QuickSort? Argue why yes or why not. 7. (10 pts) (a) What is the worst case running time for BucketSort as described in our textbook? Often it’s not easy to improve worst-case behavior, but in this case there is a simple change in the algorithm that can improve the worst case behavior by more than a constant, while still preserving the excellent expected running time of the original version. Describe how we can do this. 1 (b) You are given a set A of n numbers, each in the range [0, n − 1]. Design and analyze an algorithm that can preprocess these numbers in Θ(n) time, such that after the preprocessing, you can answer queries of the type “how many numbers in A are in the range [a,b]” for any 0 ≤ a, b ≤ n − 1 in Θ(1) time. 8. (10 pts) For some sorting algorithms there is a significant difference between the best case running time and the worst case running time. What are the best case, average case, and worst case running times for sorting n elements when using InsertionSort, SelectionSort, MergeSort, HeapSort, QuickSort, TreeSort, SkipSort? 9. [10 pts] A not very good bowling company makes bowling balls and bags. In a production run of n balls, each ball is smaller than the previous one. Similarly, in a production run of n bags, each bag is smaller than the previous one. Luckily there are n balls and n bags and each ball matches exactly one bag (and vice versa). From time to time, the order of the balls and the bags is not preserved and the packaging department has to manually match (ball, bag) pairs. By trying to match a ball and a bag we can see which one is bigger, but we cannot compare two balls or two bags directly. Design and analyze a simple algorithm to help them do this. Your first attempt may be not very efficient (e.g., O(n2 )). Then design and analyze an efficient algorithm for matching the balls with the bags. Argue that your algorithm is correct and analyze its running time in terms of the number of ball/bag comparisons. 10. You are standing along an infinitely long straight wall and it is completely dark. The fence has a single gate in it but you do not know where it is. Your goal is to minimize the distance you need to walk in order to find the gate. Design and an analyze an efficient algorithm for finding the gate, assuming you make the same size steps and the gate is n steps away from your starting position. Extra Credit Two cities A and B are 100 miles apart. More precisely, there is a perfectly straight road on the surface of the earth connecting them, and the length of that road is exactly 100 miles. Their respective city-halls are at the same elevation above sea level. The mayors of the two cities decide to connect them with a tunnel that goes straight from the basement of the city-hall in town A to the basement of the city-hall in town B. Halfway between A and B is a little village C which is also at the same elevation above sea level as A and B. To save time digging the tunnel there are going to be 4 digging crews: one working from A towards B, another from B towards A, and two more starting at the halfway point C and going towards A and B. How deep below the surface must the two crews starting at C begin their tunnels? For full credit, your calculation must be done without the help of a calculator (and it should be easy to verify its correctness without a calculator). 2

© Copyright 2020