Problem Set #5
First, we will go over the following concepts/topics using concrete examples:
- big-O, big-Omega, and big-Theta notation - proofs - worst-case analysis - thinking about recursion
Then we will try to solve the following problems using recursion:
1. Given a list of integers, write a method to find the minimum value. 2. Write a method to find the maximum value in a list. 3. Given a list of integers, write a method to return the sum of all the integers.
Note that the three problems above can certainly be solved using iteration alone. In fact, it is much easier to think about the problem non-recursively. But I think it is good practice on formulating a problem recursively and thinking about both the recursive calls and base cases for a particular recursive formulation.