The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 5
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, and Hanna Kurniawati
Problems with a ! denote tougher optional challenges and are optional in this tutorial. Only work on these problems after solving and understanding all the other problems.
Exercise 1 Left Over Questions from Past Tutorials Exercise 2 Sorting
1. Ms Sorting says that any comparison-based sorting algorithm can be made stable with the same modification scheme. Is this correct? If it is correct, please provide this scheme along with the extra computation time or memory required. If it is not correct, please provide a reasoning with counter-example.
2. Whatistheworstcaserunningtimeofbucketsort?Canweimprovethisworstcasetimecomplexity?
3. The Grinch is given the job of partitioning 2n players into two teams of n players each. Each player has a numerical rating that measures how good they are at the game. He seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between team A and team B. Show how the Grinch can do the job in O(n log n) time.
4. ! Explain how to sort n numbers with range 0 to n5 − 1 in Θ(n) time.
Hint: You might want to recall our discussion about changing basis for sorting during lecture.
Exercise 3 Abstract Data Structures: Binary Search Trees + Heaps
1. Suppose x is a leaf node in a binary search tree, and y is its parent. Must y be the successor or predecessor to x?
2. Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take O(log n) time each, but successor and predecessor now take O(1) time each. Which operations have to be modified to support this?
3. Recall the in, pre, and post order traversal in binary search tree. Assuming no duplicates in the heap, will performing one of these traversal on the heap outputs a sorted ascending and/or descending ordering of the heap elements? Please provide an explanation with proofs or counter-example.
4. Suppose you have implemented the pseudo-code for building a heap given an array of num- bers we discussed in class (slide 43 of https://cs.anu.edu.au/courses/comp3600/week5-BST_ Heaps-aftClass.pdf). And, suppose the input to your program will be the output of Mr Nice software. Mr Nice informed you that his software will output an array of numbers with no duplicate elements, and asked if you prefer his output be in the form of sorted numbers in ascending order, sorted numbers in descending order, or random ordering of the numbers. If your goal is to build the heap as fast as possible, which input form would you prefer? Please explain your choice.
5. ! Suppose x is a node in a binary search tree with two children. Can the successor of x have two children too?