Algorithm Problem Set

1. Write a recursive function that reverses a string. State its base case explicitly.

2. Compute the number of ways to climb n stairs taking one or two steps at a time. Then improve it with memoisation.

3. Explain why the naive solution to problem 2 runs in exponential time.