In this post i will show how to use the divide and conquer technique to solve problems, you may need to check previous post.

**Problem 3 (Binary search)**

Given a list of sorted integer numbers and an integer, find the occurrence of this number into the list or -1 if it doesn't exist.

**Discussion**

We can linear search for this list O(N), but with the fact that the list is sorted we can at each time get the middle element of the array and minimize the search space into either the left half part (if the searched element is less than the mid element), or the right half (if the searched element is greater than the mid element). O(lg N) where N is number of elements.

**Code**

int binary_search(vector<int> vec, int src, int dest, int elem) {

if(dest < src) return -1;

int mid = (src+dest+1)/2;

if(elem == vec[mid]) return mid;

else if(elem < vec[mid]) return binary_search(vec, src, mid-1, elem);

else return binary_search(vec, mid+1, dest, elem);

}

**Problem 4 (LargestSubsequence)**

**Topcoder**SRM 518 (DIV 1 level 1, DIV 2 level 2)

For Strings x and y, we say y is a

*subsequence*of x if y can be obtained from x by erasing some (possibly all or none) of the letters in x. For example, "tpcdr" is a subsequence of "topcoder", while "rt" is not.
Given a String

**s**, return the lexicographically largest subsequence of**s**.**Discussion**
For example if the passed string is "test" then all subsequences listed in lexicographical order are "" (empty string),
"e", "es", "est", "et", "s", "st", "t", "te", "tes", "test", "tet",
"ts", "tst" and "tt". So return "tt".

**Code**

string getLargest(string s) {

if(s.size() == 1)

return s;

string tmp = getLargest(s.substr(1));

if(tmp[0] <= s[0])

return s[0]+tmp;

return tmp;

}

**Problem 5 (Merge sort)**

Merge sort is based on the

**divide-and-conquer**paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray*A*[*p*..*r*]. Initially,*p*= 1 and*r*=*n*, but these values change as we recurse through subproblems.
To sort

*A*[*p*..*r*]:
1.

**Divide Step**If a given arrayAhas zero or one element, simply return; it is already sorted. Otherwise, splitA[p..r] into two subarraysA[p..q] andA[q+ 1 ..r], each containing about half of the elements ofA[p..r]. That is,qis the halfway point ofA[p..r].

2.

**Conquer Step**Conquer by recursively sorting the two subarraysA[p..q] andA[q+ 1 ..r].

3.

**Combine Step**Combine the elements back inA[p..r] by merging the two sorted subarraysA[p..q] andA[q+ 1 ..r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A,p,q,r).

**Code**

vector<int> merge(vector<int> a, vector<int> b) {

vector<int> res;

int sz = (a.size()+b.size()), i = 0, j = 0;

a.push_back(INT_MAX);

b.push_back(INT_MAX);

while(res.size() < sz) {

if(a[i] <= b[j]) {

res.push_back(a[i]);

++i;

}

else {

res.push_back(b[j]);

++j;

}

}

return res;

}

vector<int> merge_sort(vector<int> A) {

if(A.size() <= 1) return A; // Already sorted

vector<int> left, right, res;

int i, mid = A.size()/2;

for(i = 0; i < mid; i++) left.push_back(A[i]);

for(i = mid; i < A.size(); i++) right.push_back(A[i]);

left = merge_sort(left);

right = merge_sort(right);

res = merge(left, right);

return res;

}

In the next post i will show sample problems solved using the Dynamic programming technique.

## No comments:

## Post a Comment