Month: January 2014

Revising Recursion

I was going to write about Backtracking this time. But then I thought that it would be better to post about recursion first as it is a very important weapon. Algorithms such as Backtracking, Depth First Search, Disjoint Set Union (also known as Union Find), Segment trees and many other graph algorithms are best implemented using recursion.

Recursion is when a problem is defined in terms of smaller instances of the same problem. A very well known example is the factorial of a number. We can define factorial of a number in two ways.
First is the iterative way,
factorial(n)= product(i=1 to n) ( i )

The second way is the recursive way,
factorial(n)=n*factorial(n-1) .

Of course, both the definitions lead to the same values. In the recursive definition, the factorial of n is shown in terms of factorial of (n-1) (i.e. in terms of a smaller factorial problem).

Programs implemented using recursion can be incredibly short and at the same time incredibly difficult to understand. So it’s essential that some properties of recursion are understood properly before starting the algorithms I mentioned in the start of my post.

Let’s look at the code for factorial of a positive number, n. The code is pretty straight forward.

long long factorial(long long n)
{
  if(n==0)
    return 1;
  long long a=factorial(n-1);
  return n*a;
}

A recursive function is one that can call itself.

When a function is called, we say that an instance of that function is created.

Here, factorial() is a recursive function. Note that, it has a call to itself in its body. factorial() is capable of calling itself, and the call at line 5 is called a recursive call.

When a function calls itself, a different instance of that function is created whose variables are completely different than the calling function. Eg. if I want to find 4!, I will call factorial(4). factorial(4) will in turn call factorial(3). The variables ‘n’ and ‘a’ are different for both these instances of factorial(), i.e. the variables have different locations in memory and store different values. For the first one n=4 and for the second one n=3.

All instances of factorial() will execute completely independent of each other. One instance of factorial doesn’t care about the value of ‘n’ or any other variable in other instances of factorial().

For an instance of a recursive function to terminate, all its child instances should first terminate. Eg. For factorial(4) to terminate, first its child instance i.e. factorial(3) should terminate.

recursion_factorial

Recursion depth:

An instance of a recursive function is said to be at depth d, if there are d instances of that function present above it.
In the previous example, factorial(4) is at depth 0, factorial(3) is at depth 1, factorial(2) is at depth 2, factorial(1) is at depth 3 and factorial(0) is at depth 4.

Consider the following code snippet:

void func(int depth)
{
  if(depth==10)
  {
    printf("reached depth of %d, now returning back",depth);
      return;
  }
  printf("at depth %d\n",depth);
  func(depth+1);
  printf("returning from depth of %d\n",depth);
}
int main()
{
  func(0);
  return 0;
}

In this code, we are limiting the maximum depth to which func() can be recursively called to 10.
Keep in mind that each instance of func() has different ‘int depth’ variable.
Notice how we are passing an incremented value of depth in the recursive function call func(depth+1).
This is a very common technique to increment values while calling recursively.

An infinite recursion is also possible which is just like an infinite loop. Suppose I forgot to increment the depth while passing it:

void func(int depth)
{
  if(depth==10)
  {
    printf("reached depth of %d, now returning back",depth);
      return;
  }
  printf("at depth %d\n",depth);
  func(depth);//notice the lack of +1 here
  printf("returning from depth of %d\n",depth);
}
int main()
{
  func(0);
  return 0;
}

This code will run until eternity as the condition that ends the recursion is never met.
Okay, so this covers the basic terminology and few techniques.

As an advanced example, lets write a program to find all length n permutations of the digits 1,2,3 using recursion.

int permutationcount=0;
void permute(int atdepth, int n, int selections[])
{
  if(atdepth==n)
  {
    int i;
    printf(“Permutation %d: “,permutationcount);
    for(i=0;i<n;i++)
      printf(“%d “,selections[i]);
    printf(“\n”);
    permutationcount++;
    return;
  }
  selections[atdepth]=1;
  permute(atdepth+1,n,selections); // select 1 for current position
  selections[atdepth]=2;
  permute(atdepth+1,n,selections); // select 2 for current position
  selections[atdepth]=3;
  permute(atdepth+1,n,selections); // select 3 for current position
  return;
}
int main()
{
  int a[1000],n;
  scanf(" %d",&n);
  permute(0,n,a);
  return 0;
}

See the following image to understand the order of function calls:
recursion_permute

A few important observations:
1. An instance of the recursive function permute() at depth d sets the value of selections[d], i.e. the (d+1)th position in the final permutation. And then calls permute() again to compute the rest of the permutation.
2. Each instance of permute() contains three recursive calls within it. Each one represents a different selection of number for the current position.
3. When a depth of n is reached, n numbers have been set in the selections[] array. And the array is printed.
4. A recursion depth of n is reached 3^n times. Because there are 3^n permutations possible.
5. Global variables are preserved among all the recursive instances of permute(). The variable permutationcount is used to keep track of the number of permutations.

For a particular instance of permute(), the call at line 17 will be executed only when the call at line 15 (along with all the subsequent calls that arise from inside it) complete execution.
And the call at line 19 will be executed only when the calls at lines 15 and 17 (along with all their respective subsequent calls) complete execution.

Recursion may seem overwhelming at first and it may take time for you to get used to it. But once you get the hang of it, there’s nothing more wonderfully magic in programming than recursive functions. Don’t give up on them just because they seem difficult at first sight.

Algorithm #5: Binary Search and its relatives

I think most of you already know about binary search. It is an algorithm that is used to search an element in an array. Its complexity is O(log n) as opposed to O(n) for linear search, so it’s a much better way to search an array. This time I’ll first revise binary search and then I’ll show how simple modifications in the basic binary search algorithm can produce interesting variants.

1:  BINARY SEARCH

Assume that we have got an array of n integers, and we have to run many queries on the array. In each query, we are given a number ( named targetnum ) and we have to tell if the number is present in the array or not. We’ll use binary search to solve this.

The first step of this algorithm is to sort the array. At first look, it may seem that sorting will consume a lot of time and will contribute to overhead. But, remember that we have to run MANY queries on the array. This means that sorting once will give advantage for each of the many queries. So, ultimately the overhead contributed by sorting is much less than the advantage it gives.

Now, when we start searching, targetnum can be present anywhere in the sorted array. We take a look at the integer that is present in the middle of the array. If this middle integer is targetnum itself, then our search terminates. If this middle integer is greater that targetnum, then we can say that targetnum is obviously present somewhere in the first half of the array (i.e. in [first,mid) ) (this is because the array is sorted). And if the middle integer is less than targetnum, then targetnum is present somewhere in the second half of the array (i.e. in (mid,last] ).

The potential space ( i.e. the space where targetnum can be present ) is, therefore, reduced to half in every step.

We repeat this process until the size of the potential space becomes 1. And if we still have not yet found the targetnum, we can conclude that it is not present in the array.

In form of C code, this algorithm will look something like:
binarysearch() is a function that takes the array, the size of the array and the integer to be searched as arguments.
If there is even a single instance of targetnum in the array then 1 will be returned, otherwise 0 will be returned.

int binarysearch(int *a,int n,int targetnum)
{
  int start=0, end=n-1, mid; 
  while(start<=end)
  {
    mid=(start+end)/2;
    if(a[mid]==targetnum) // if the middle element is the required number, then search terminates
    {
      break;
    }
    else if(a[mid]>targetnum)
    {
      end=mid-1; // restrict search to first half
    }
    else if(a[mid]<targetnum)
    {
      start=mid+1; // restrict search to second half
    }
  }
  if(start<=end)
    return 1;
  else
    return 0;
}

This algorithm halves the potential space in every iteration. So, it takes a maximum of log2(n) iterations to complete the search of one element, as opposed to n iterations per query for linear search.

2,3: LOWER BOUND AND UPPER BOUND

A variant of binary search can be used to find the lower bound and upper bound of an element (say, targetnum ) in a sorted array.

Lower Bound: The lower bound of targetnum is the first element in the sorted array that is not less than targetnum.

Upper Bound: The upper bound of targetnum is the first element in the sorted array that is greater than targetnum.

Explanation: It is possible that targetnum may have no instance, a single instance or multiple instances in the array.
If there is only one instance of targetnum present in the array, lower bound will be the position of that instance, and upper bound will be the position of that instance + 1.

If there are multiple instances of targetnum present in the array, lower bound will be the position of the first instance, and upper bound will be the position of the last instance + 1.

If there is no instance of targetnum in the array, lower bound and upper bound both will be the position of first integer greater than targetnum.

So, if the sorted array is {1,4,5,5,5,6,9,9,10}, then the lower bound and upperbound of each integer will be:

Number Lower Bound Upper Bound
0 0 0
1 0 1
2 1 1
3 1 1
4 1 2
5 2 5
6 5 6
7 6 6
8 6 6
9 6 8
10 8 9
11 9 9

(Note that in case of 11, the lower bound and upper bound are 9, i.e. last index of array + 1. This is so because 11 is greater than all the elements of array)
The code for finding lower bound:
lowerbound() is a function that takes the array, the size of the array and the element whose lower bound has to be found as arguments and returns the lower bound of the given element.

int lowerbound(int *a,int n,int targetnum)
{
    int first=0,last=n-1,mid;
    while(first<last)
    {
        mid=(first+last)/2;
        if(a[mid]==targetnum)
        {
            last=mid;
        }
        else if(a[mid]>targetnum)
        {
            last=mid-1;
        }
        else if(a[mid]<targetnum)
        {
            first=mid+1;
        }  
    }
    if(a[first]>=targetnum)
        return first;
    return first+1;
}

The main difference between binary search and this algorithm is when the condition a[mid]==targetsum is true. See line 9 of the code. In the binary search algorithm, if a[mid]==targetnum is true, the search ends (as the required number was found). But here, we are instead interested in the first instance of targetnum, so we continue our search.
If there is an instance of targetnum present at position mid, then it means that the first instance of targetnum must be in the interval [first,mid].

After the while loop ends, the required position is either the value in first or first+1.

The code for finding upper bound is:
upperbound() is a function that takes the array, the size of the array and the element whose upper bound has to be found as arguments and returns the upper bound of that element.

int upperbound(int *a,int n,int targetnum)
{
    int first=0,last=n-1,mid;
    while(first<last)
    {
        mid=(first+last)/2;
        if(a[mid]==targetnum)
        {
            first=mid+1;
        }
        else if(a[mid]>targetnum)
        {
            last=mid-1;
        }
        else if(a[mid]<targetnum)
        {
            first=mid+1;
        }
    }
    if(last>=0 && a[last]>targetnum)
        return last;
    return last+1;
}

The main difference between this algorithm and binary search is when the condition a[mid]==targetnum is true. Here, we are interested in the last occurrence of targetnum.
So, if one instance of targetnum is present at mid, then the last instance must be present somewhere in the interval [mid,last].

After the while loop ends, the required position is either the value in last or last+1.

APPLICATION:
One of the possible interesting applications of upperbound() and lowerbound() is:
If we are told to find the number of occurrences of a given integer (say, targetnum) in an array, we can use lowerbound() and upperbound() to find the answer.
The answer will be upperbound(a,n,targetnum)-lowerbound(a,n,targetnum).
Convince yourself that this query is correct by consulting the definitions of upper bound and lower bound given earlier in this post.
This query will have time complexity O(log n) as both the functions take about log n iterations each to find the answer.

DEEPER INSIGHT:
1. For the ones who observed line 9 of upperbound() closely: There are two reasons for which I used first= mid+1, instead of first = mid.
Firstly, using first=mid will lead to an infinite loop in some cases (eg. when first=1 and last=2).
Secondly, we are interested in (the position of last instance of targetnum) + 1, so its alright if targetnum itself is not present in the active range.

4:
There is another type of binary search; one that is not done on any array. There are situations where you need to optimize a certain parameter. You know the minimum and maximum value the parameter can take but there seems to be no other way than iterating over the possible values to find the optimal value. In certain cases, brute force iteration can be avoided and binary search can be used to solve the problem. One recent example of this type is the “PROBLEM A: ARROWS AND QUIVERS” question in ACM ICPC2013 Amritapuri site.
Discussing this topic will make this post complicated and much too lengthy. I’ll write about it in my future posts.
ACM ICPC 2013 Amritapuri questions
Solution to problem A

QUESTIONS ON BINARY SEARCH:

Am I A Fibonacci Number (Simple)
Codeforces:Eugeny and Play List (Easy)
Codeforces:Primes on Interval (Medium)

If you feel that some point wasn’t explained properly, please comment below and I’ll try to fix it.

Algorithm #4: Bit Masking

First of all, I’d like to apologize for not having posted anything at all since so many weeks. I’ll try to be fairly regular from now.

The topic that I am going to discuss now is called Bit Masking. This technique is useful when you have a set and have to select a subset from it that satisfies a particular condition.  The following would be a nice example. It is called the ‘Subset Sum Problem’.

You have n coins with you; each coin has a particular value. You want to select some coins such that the sum of value of the selected coins is m.

So, each coin can have one of two fates: either it is selected or it is not. Lets solve this problem for n=4, m=10 and the value of coins as 2,3,5,7. There are a total of 2^4=16 subsets possible. In other words, there are 16 ways of selecting coins.

Let me draw your attention to an interesting fact. When you count from 0 to 15 in binary, you obtain all the possible length 4 permutations of 0s and 1s. We shall use this fact to generate all the subsets of {2,3,5,7}. Each of the numbers from 0 to 15 will represent a different subset of the set {2,3,5,7}. For instance, the number 14 (1110 in binary) represents the subset {2,3,5}, the number 10 (or 1010 in binary) represents the subset {2,5}, and 15 (1111 in binary) represents {2,3,5,7} and 0 (or 0000 ) represents {}. So, if the ith bit in the binary representation is 1, then the ith number in the set is selected otherwise it is rejected.

Just for clarity, I’m listing below the subset that each number represents:

Initial set= {2,3,5,7}

Number Its Binary Subset it represents
0 0000 {}
1 0001 {7}
2 0010 {5}
3 0011 {5,7}
4 0100 {3}
5 0101 {3,7}
6 0110 {3,5}
7 0111 {3,5,7}
8 1000 {2}
9 1001 {2,7}
10 1010 {2,5}
11 1011 {2,5,7}
12 1100 {2,3}
13 1101 {2,3,7}
14 1110 {2,3,5}
15 1111 {2,3,5,7}

So, to find the answer for the initial problem, all we have to do is iterate a variable (say, i) from 0 to 15; during each iteration find the subset that i represents and then check if it satisfies the condition.

The code will look something like

#include<stdio.h>
int main()
{
    int n,coins[10000],j;
    long long m;
    scanf(" %d %lld",&n,&m);
    long long last=(1<<n)-1; // generalizing, we have iterate from 0 to 2^n - 1
    long long i,temp,currentsum;
    i=0;
    while(i<n)
    {
        scanf(" %d",&coins[i]);
        i++;
    }
    for(i=0;i<=last;i++)
    {
        temp=i; //stored i in a different variable to save it from modification
        currentsum=0; // to keep track of the sum of values of selected coins
        j=0;
        /*-----SUBSET GENERATION PROCESS START-----*/
        printf("Checking subset : { ");
        while(j<n) // for each bit of temp
        {
            if(temp%2==1) //examining the last bit (LSB) of temp. If it is 1, we take the coin
            {
                printf("%d ",coins[j]);
                currentsum+=(coins[j]);
            }
            temp>>=1; //right shifting temp, so that we may analyze the next least significant bit in the next iteration of while loop
            j++;
        }
        /*-----SUBSET GENERATION PROCESS OVER-----*/
        printf("} Sum= %lld",currentsum);
        /*-----CONDITION EVALUATION FOR THE CURRENT SUBSET-----*/
        if(currentsum==m)
        {
            printf("Found solution subset");
            //break;
        }
        /*-----CONDITION EVALUATION OVER-----*/
        printf("\n");
    }
    return 0;
}

The body of the outer ‘for’ loop can be changed in accordance to what the problem is. In this case, we just needed the sum of numbers of each subset, so I did a running total of the value of coins selected. And when we obtain the sum of that subset, we check if it is equal to m. I’ve added printfs in the code at various places to make things clearer. Try it out by running it on your machine.

There is an obvious drawback to this method. As we are examining all possible subsets, this is a brute-force approach. If n becomes greater than 25 this method will be very slow. And, of course, we also have the limitation that we cannot have an integer larger than 64 bits in C/C++, so this method will not work for n greater than 64 ( though, as mentioned earlier, the method already becomes impractical at around n=25) .

There exists no efficient algorithm for Subset Sum problem. We may optimize our algorithm in many different ways, but a perfect solution has not yet been discovered. All algorithms that exist currently will become slower and, therefore, inefficient very quickly as n increases. Bit Masking is one of the many solutions that exist currently. There are many other, more efficient solutions (comparatively more efficient) that are quite complex to be discussed currently.

In a nutshell, this method is very easy to code and is very good for programming competitions if n is small enough. There is an alternate method very popular in competitive programming called ‘Backtracking’ which I’ll discuss in future.

If you want to practice bit masking then follow these links:

http://www.codechef.com/problems/MARCHA1 (Simple)

http://www.codechef.com/problems/LEALCO (Medium difficulty)

NOTE:
1. For those who are comfortable with the notation of complexity, the computational complexity of this algorithm is O(n*2^n)
2. Lines 26 and 27 in the code may just as well been

printf("%d ",coins[n-j-1]);
currentsum+=(coins[n-j-1]);

because it doesn’t matter if you start counting the bits from the left or from the right