Peak Finding

2011-09-29T08:38:00.002-05:00

A few days ago I decided to run through some exercises in C (since I am teaching myself it) and analyze some of the common algorithms that are explored in general Comp Sci programs. "Introduction to Algorithms" by Thomas Cormen, Charles Leiserson & Ronald Rivest is pretty much the standard go-to book. Coincidentally, a few months back I also found a post on Hacker News that was the class material for the MIT course that accompanies the book. It helps that the algorithms have been translated to Python, although the code language shouldn't matter, it eases me translating it to C which I am fairly new at.

Anyways, one of the first algorithms is peak finding (a sort of binary search algorithm that returns peaks). That is, given an array on n numbers what number is the largest? The final example the slides give is a peak function called peak1d which recursively splits the array into two halves and compares the elements around that midway point which should eventually yield the peak in the array. The code reads:

peak1d(A, i, j):
m = (i+j)/2
if A[m-1] <= A[m] <= A[m+1]:
return m
elif A[m-1] > A[m]:
return peak1d(A, i, m-1)
elif A[m] < A[m+1]:
return peak1d(A, m+1, j)

The goal of this algorithm is to somewhat find everything considered a 'peak' within the array. That is it is a number that is higher than the numbers that reside either directly to the right or left of it.

There are a few things that (I think) fall short in this code (having to split the array into two before sending it to the algorithm and then comparing the two halves, finding peaks but not necessarily THE PEAK, multiple peaks in the two halves, etc) but the biggest most interesting one I saw was handling the ends of the array. That is given an array with indexes 0,1,2,3,4,5; what if positions 0 or 5 hold the maximum number? The array would be out of index when trying to compare the first if statement and if translated to C, the return of index A[6] would return garbage.

So in exploring C, I though I would take a hack at modifying the algorithm to accept the ends at peaks and focus on the highest peaks rather than a series of them. So I somewhat digress, because the above algorithm actually works exactly like intended by finding the peaks in an array and returning them but it seems somewhat impractical. Below is the C code I came up with:

int peak(int a[], int s, int e){
int l, r;
int d = e-s;
if(d > 1){
// recursive clause for too many values to compare
int m = (s + e) / 2;
l = peak(a, s, m-1);
r = peak(a, m, e);
} else if (d == 1){
// compares two values when only 2 are sent
l = a[s];
r = a[e];
} else if(d == 0){
// handles singular values upon odd arrays
return a[s];
}
return (l > r) ? l : r;
}

This algorithm takes the entire array along with the 0 index and the (length of the array - 1) to start and then recursively reduces the range of the array by half and finds the peak for each half. This essentially boils down to returning the bigger of two specific values in the left half of the array and then comparing it to the largest value in the right half of the array. It's an interesting algorithm and took some thought to catch the edges of the array and handle a dynamic array size whether it be even or odd. In the end, the effort seems somewhat futile. If you do the math if the array is n numbers long, then you have to still page through n-1 items in the array no matter what. This is only one time better than if you where to apply a linear algorithm to such an array to find the peak where the paging length would be n instead:

int lpeak(int a[], int c){
    int m = 0, i;
    for (i = 0; i < c; i++){
	if (a[i] > m){
		m = a[i];
	}
    }
    return m;
}

What does that mean? As n grows to say 1000, the reduction in calculation time of my "halves" algorithm diminishes, and the additional complexity of the code and general ugliness of it makes it something you would never want to use or maintain. In addition, the recursive nature of my solution also replicated the array n-1 number of times, with which a large array would cause massive overhead.

I guess there is not really a conclusion to this post other than analyzing my findings. The main take away from it for me was one, have an end goal so that you solution isn't a digression of the original topic (mistake A I made) & two is that it just reiterates how simple, clean code allot of time ends up being better code too.

Until next time, here's a photo of some empty London Guard Booths:

Again...

2011-09-15T12:16:00.002-05:00

Hello World,

Sorry for switching it up again. Posterous dramatically complicated how to post on their platform so I decided to drop that and migrate back to the old comamitc blog... this one has been alive since August 2006 when I moved to Midwestern State University in Wichita Falls, TX. Boy allot's changed since then.

I don't really ride bikes anymore. Well not even really. I don't ride bikes anymore. Not to say I don't want to but the last few Months haven't been very conducive to that seeing as I'm living in Germany and it just doesn't make a ton of sense to get deeply rooted in some place that isn't my home country.

I think I worked in a bike shop last I posted as well. After a few lucky career moves in my last few years of college I found myself in the IT industry and mostly centered around Oil and Gas (go figure with Houston and all). The opportunities have really helped me gain some traction in direction and for the first time in my life I feel like I can say, I don't want to do that... Somewhat of the different mentality I previously had where just about everything interested me.

I read a few books along the way, met a few people, had old friends make further impressions and eventually... well here I am. I think there is probably just a little too much that's happened in the space that gaps my blog posts, so we will all just have to sit back, enjoy the ride, stay in touch and at the very least be amused with poor grammar.

I think I'll get in the habit of concluding posts with cool pictures. Here is one of the most amazing person on the planet:

~ Mitch