## Archive for the ‘scripts’ Category

### A small OpenMP practice

Monday, October 21st, 2013

I had to parallelize a piece of code. The requirements were, single node with multiple cores, RAM might be limited based on data sets. OpenMP seems a good fit for my purpose, here is my solution:

```
{
int block = (int) N / (double) total_threads;
int start = ID * block;
int end = (ID + 1) * block;
if (ID == (total_threads - 1)) {end = N;}

VpTree* tree = new VpTree(X);

for(int n = start; n< end; n++) {
search(n, tree);
}
delete treeC;
}

```

At beginning, the start and end for the loop segment are manually defined. Well, this is not necessary in some cases since one could use

```	#pragma omp parallel for
for(int n = 0; n< N; n++) {
search(n, tree);
}```

But the problem was that, in “search()” there are a bit messy/complicated/un-neat reading of the pointer tree. So I always ended up “Segmentation fault”. That’s why I was duplicating the pointer “tree” for each thread. The max number of threads allowed is pre-defined in order to comply with RAM issues. There might be more elegant solution, but I’m easy to satisfy.

Last but not least, I benefited a lot from the presentation of Tim Mattson and Larry Meadows from Intel: A “Hands-on” Introduction to OpenMP.

### Interview series II: sum of two elements

Wednesday, June 29th, 2011

I was asked such an interview question.

Given an unsorted array of positive integers, and also a target value K, find two elements that sum up to K.

So I suggested, sort the array first, and then start from the last (maximum) element that is smaller than K, x_max and then use binary search to find K-x_max. Well the complexity for sorting is O(n log n) and for finding is another O(n log n). Any improvement if the array is sorted? I stuck there, 5 seconds later, he tipped me with something like how about using two index pointers. WOW, great hint. Now the complexity for this step is O(n). Below is one solution.

```#include <iostream>

using namespace std;

void quickSort(int *arr, int left, int right) {
if(left>=right) {return;}
int Start=left;
int End = right;
int pivot=(left+right)/2;
int pivotV=*(arr+pivot);
int tmp;

while(left<right) {
if(*(arr+left) <= pivotV) {
left++;
}
if(*(arr+right)>=pivotV) {
right--;
}
if(*(arr+left)>pivotV && *(arr+right)<pivotV) {
tmp=*(arr+left);
*(arr+left)=*(arr+right);
*(arr+right)=tmp;
left++;
right--;
}
}
*(arr+pivot)=*(arr+right);
*(arr+right)=pivotV;
quickSort(arr, Start, left-1);
quickSort(arr, right+1, End);
}

void ksum(int *arr, int len, int k) {
int left, right, ktmp;
left=0;
right=len-1;
while(left<right) {
ktmp=*(arr+left)+*(arr+right);
if(ktmp==k) {
cout << *(arr+left) << " + " << *(arr+right) << " = " << k << endl;
return;
} else if(ktmp>k) {right--;} else {left++;}
}
cout << "Couldn't find the two elements!\n";
return;
}

int main() {
int a[10]={10,3,4,9,8,7,2,1,5,6};
quickSort(a, 0, 9);
ksum(a, 10, 12);
return 0;
}```