Week 8: Exercises

1. I/O Reversal

Write a procedure reverse that reads a sequence of whitespace-separated integers until the end of input and writes them out in reverse order, with one space between integers in the output. Use a stack.

2. Balanced Parentheses

Write a function balanced(s: string): boolean that takes a string containing only the characters '(', ')', '[' and ']' and returns true if the string contains a balanced set of brackets, where each opening bracket (i.e. '(' or '[') is paired with a closing bracket of the same type. For example:

• ( [ [ ] ] ( ( ) ) ) → true

• [ ( ) ( ] [ ) ] → false

3. Lots of Merges

Consider the mergesort procedure from class. Suppose that I call mergesort on an array of length N = 2^k. How many times will mergesort be called (including the top-level call)? How many times will merge be called? Suppose that we could magically perform the merge operation in constant time, for any two input arrays. How long would mergesort then take to run?

4. Adaptive Mergesort

Mergesort as described in class has both a best-case and worst-case running time of O(N log N). Can we modify it so that it is adaptive, i.e. runs more quickly when the input array is already sorted or nearly so? If so, what is the new best-case running time?