Activity Sheet 8

Manager

name:

Recorder

name:

Speaker

name:

Section 5.1

1. Consider the problem of finding the location of the largest element in an unsorted array (if many elements achieve that largest value, return the first of them).
   1. Write a brute-force algorithm for this problem, and determine its time complexity.
   2. Write a recursive decrease-by-one-and-conquer algorithm for this problem, and determine its time complexity via a recurrence relation (and optionally using the master theorem, or solving directly).
   3. Write a divide-and-conquer algorithm for this problem, and determine its time complexity via a recurrence relation and using the master theorem.