2D Greedy Ascent Search Algorithm Clarification

user_8423297 0
Viewed 2528

I am doing some remedial work on algorithms as I am taking a graduate course on them in the Fall and was a physics undergrad. Watching this video and at the 38:00 mark he goes over the greedy ascent algorithm for a 2D array. I am confused as he defines the peak as a <= b,c,d,e (with b,c,d and e being the elements to the left,right,top,bottom of the current element 'a'). And then he goes on to say that to find the peak you follow the greatest element bordering on 'a' but what if you have the 2D array:

20 15 13
12 10 10
40 40 40

and started at 13, wouldn't the greedy ascent algorithm incorrectly identify 20 as the peak? How can you search an unsorted array without having to look at every element?

I thank you for your help apologize in advance if this is a silly question.

search arrays algorithm
3 Answers

I am also taking that course and peak as he defines it is, an element say 'a' that is greater than any element bordering it.

Greedy Ascent Algorithm

here, 'a' may or may not be global peak [bigger than all elements in the matrix]. what ever the algorithm finds faster it will give that to us provided it matches the conditions above.

There is some confusion about what peak finding is actually finding. It is easily mistaken as the biggest element in the array/matrix but really depends on the question being asked. If the question doesn't specify what peak is, it is generally taken to be the element abiding by above conditions waiting to be found by an algorithm.

Look at this: Greedy Ascent Algorithm GIF

user_148214770
Related