Exercise 1                                                                     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. What is the worst case running time of bucket sort? Can we improve this worst case time complex- ity?

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(nlog n) time

Exercise 2                              Abstract Data Structures: Binary Search  Trees

1. Suppose x is a leaf node in a Binary Search Tree, and y is its parent. Must y be the successor of x? Must y be the predecessor of x? Could  x be the successor (resp. predecessor) of y? Answer all four questions by providing a counter example if the respective answer is‘no’, and provide an explanation (better yet: a proof!) if the respective answer is‘yes’.

2.  ! Suppose 北 is a leaf node in a Binary Search Tree, and y is its parent (again).

• Now assume 北 is the left child of y . Is y the successor of 北?

• Likewise assume 北 is the right child of y . Is y the predecessor of 北?

• Now we assume neither again. (I.e., we don’t know whether 北 is y’s left or right child.) Must y be the successor or predecessor to 北?

3. We now re-visit the pre-, in-, and post-order traversal of Binary Search Trees.

• Please explain the properties of the resulting key sequences by each of these algorithms. You may refer to properties of the tree (like the level in which the respective key occurs in the tree).

•  ! Prove or provide a counter-example (which is also a proof) whether the respective algorithm (consider all of them) generates an ascending or an descending order of keys. Assume that all keys are unique. (Note that this encompasses six questions.)