Notes from CS2040S Week 2 Lecture 2

CS2040S_w2l2.md

CS2040S Week 2 Lecture 2

Notes from Week 2 Lecture 2 on Data Structures and Algorithms.

Problem Solving

Peak Finding

Aim is to find the global maximum and ignore local maxima.

inputs: Array A[0 ... n-1]
output: Maximum element in A

Typical best searching runtime for global maximum is O(n).

Traversing from the start

1. Start from A[1]
2. Examine every element
3. Stop when you find a peak

The runtime is still O(n). To find local maxima, we can do better.

Traversing outwards from the center
The worst-case cost will be O(n/2). Move outwards from the center to the ends as long as the values are increasing in nature.

• If the left half starting value is less than the middle value, we can ignore it. Same for right.
• This helps reduce the search space
• The array does not need to be sorted
• Repeat by starting at the middle of the chosen half

This is alright is the algorithm is to just choose one peak and not all of them.

if A[n/2] is a peak
	return n/2
else if A[n/2 + 1] > A[n/2] # look at next
	# search in right half
else if A[n/2 - 1] > A[n/2] # look at prev
	# search in left half

Key Property – Invariant
If we recurse in the right half, we assume that there exists a peak. This holds for any range [begin, end]. Every peak in the right half is a peak in the whole array.

To prove it, assume there is no peak in the right half. This means the mid < mid+1 < mid+2 < mid+3 ... < mid+k = n-1. This means the element at position mid+k (end of the array) is a peak by definition. By contradiction, there is a peak in the right half.

For instance, if the right half includes [23, 24, 25, 26], the algorithm will show that 26 is the peak.

Steep Peaks
To find an element that's strictly larger than its neighbours, like [7, 7, 7, 7, 7, 8, 7], we need the algorithm to find 8. This might go well if the peak is in the last index.

This will fail since the algorithm doesn't know which direction to traverse ie. left or right. Since the left and right of 7 are the same values. There is no indication of which half to go to.

Though, one fix is to recurse on both halves instead by adding another condition that checks if A[n/2 - 1] == A[n/2] == A[n/2 + 1]. This will become a O(n) linear time algorithm and is expensive.