Problem solving techniques (Example problems) (Cont.)

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 array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[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.