MA214 Algorithms and Data Structures

Exercise 1.1.  The one-dimensional peak problem 1 pt

Consider the problem of finding the index of the peak of a sequence of n ≥ 2 distinct integers that is first increasing and then decreasing. A peak element is one that is larger than its immediate neighbours. The first and last element just need to be larger than their single neighbour.

Following the example of the sorting problem in the lecture, formally define this com- putational problem.

Exercise 1.2.  A slow iterative algorithm                                                                     4 pt

The one-dimensional peak problem can be solved by an iterative algorithm, which scans through the sequence once.

(a) Describe this algorithm in words. Be careful and make sure your algorithm han-dles all boundary cases correctly.

(b) Implement your algorithm in Python. And test it on three sequences, one where the peak is at the beginning, one where it is in the middle, and one where it is at the end.

(c) For a sequence of length n  ≥ 2, what is the minimum and maximum number of comparisons that your algorithm has to perform?

Exercise 1.3.  A faster recursive algorithm 5 pt

A faster algorithm for the one-dimensional peak problem can be obtained by following the divide-and-conquer paradigm. The basic idea is to recursively split a problem of size n into a single problem of size roughly n /2.

(a) Describe this algorithm in words. Again, be careful that your algorithm handles all boundary cases correctly.

(b) Implement your algorithm in Python. And as above, test it on three sequences, one where the peak is at the beginning, one where it is in the middle, and one where it is at the end.