Puzzle – Easy : C++ Multithreading

Below is a small and easy puzzle on multi-threading, ideal for beginners. And to be honest, title should have been “C Multithreading” since it uses pthreads, and not C++11 for threading.

#include <pthread.h>
#include <unistd.h>
#include <iostream>

using namespace std;

int i;

void* f1(void*)
{
    for (i = 0; i < 10; i+=2){
        cout << i << endl;
        sleep(1);
    }
    return 0;
}

void* f2(void*)
{
    for (i = 1; i < 10; i+=2){
        cout << i << endl;
        sleep(1);
    }
    return 0;
}

int main()
{
    pthread_t t1, t2;
    pthread_create(&t1, 0, f1, 0);
    pthread_create(&t2, 0, f2, 0);
    pthread_join(t1, 0);
    pthread_join(t2, 0);
}

So what would be the output? In what order numbers will be printed? That’s the small puzzle for you.

To make you really think, I won’t give answer. You are free to share your answer in comments though. And hey running the program without thinking would be considered cheating!

Don’t you cheat!

Posted in Programming | Tagged , , | Leave a comment

String’s length

vinayakgarg:

A simple short gotcha!, worth knowing.

Originally posted on Andrzej's C++ blog:

Let’s start with a small test. Is the following assertion correct?

1

It is not; otherwise I wouldn’t be mentioning this in the post; but do you know why it is wrong?

View original 166 more words

Posted in Programming | Leave a comment

Don’t do srand(time(0)) while testing!

This is my smallest post, but extremely important. In C or C++, before generating random numbers we often end up doing

srand(time(0))

So every time you run the program, you get new set of random numbers. Do you see the problem?

The problem is that the output is not reproducible. This is a big issue if you want to debug a particular test case.

But for some purposes, you just don’t need to reproduce output, in that case go ahead and use it. In some of my (blog) programs I am guilty of using srand(time(0)), please disregard it.

Posted in Programming | Tagged | 2 Comments

Some important GCC flags

GCC is a well known compiler for a number of languages. Here I will list and describe some important flags used with GCC, relevant for C and C++.

-o

This is used to set the output file. Notice that it is small case ‘o’, not zero or upper case ‘O’. If the flag is absent, the output file is a.out 

gcc -o myprog mycode.c
g++ -o myprog mycode.cpp

-g

This is used to produce debugging information with output. This information can be used by debuggers like gdb, for debugging the program. I will advice against using this flag with optimization flag (below).

gcc -g mycode.c
g++ -g mycode.cpp

-Wall

This is a highly recommended flag for all programs. It turns on all optional warnings. Such as “unused variable” warning. Needless to say you can ignore warnings, but a good programmer would want to know all warnings raised and fix them.

gcc -Wall mycode.c
g++ -Wall mycode.cpp

-O

This is the most important flag. It controls optimization. While it can’t convert O(n2) solution to O(n) ;) it certainly can reduce running time drastically. See time comparison below. Notice that it is capital ‘O’, not zero. There are 3 levels (or rather 4) of optimization-

  1. -O1 : This tries to reduce execution time and code size. Thus it takes more time than usual. One example of optimization – transform conditional jump into branch-less equivalent.
  2. -O2 : This optimizes even more than -O1. Hence even better performance and more compilation time. For most purposes I use this flag for optimization.
  3. -O3 : Optimizes even more than -O2.
  4. -Os : This is little different, in that it optimizes for code size instead of execution time. But smaller code size also helps to reduce execution time.
gcc -O1 mycode.c
g++ -O1 mycode.cpp

I compiled the program to find prime numbers (using Sieve of Eratosthenes) with different optimization levels, here are various execution times and executable size-
Without optimization : 1.835 sec, 25.2 KB
-O1 : 0.489 sec, 13.7 KB
-O2 : 0.472 sec, 13.7 KB
-O3 : 0.460 sec, 17.5 KB
-Os : 0.573 sec, 13.9 KB

Now I warn you, don’t jump to any conclusion from these stats, they are just for showing that these flags are not useless :P

-std=

Used to set the language standard. Both C and C++ have several standards, like C++11, C++98, C99, C89. This flag is absolutely necessary if you want to use C++11 features, as its features are experimental currently in gcc and not available by default.

gcc -std=c99 mycode.c
g++ -std=c++11 mycode.cpp

Below flags are less important, but still useful to know.

-D

Sometimes one needs to add #ifdef/#ifndef gaurds in code. For this I find -D flag extremely useful. It pre-defines a macro with definition 1. See example-

gcc -D DEBUG mycode.c
g++ -D DEBUG mycode.cpp

Above flag is equivalent to adding following line in C/C++ code

#define DEBUG 1

-pg

If you want to profile your code using gprof, you need to pass this flag.

gcc -pg mycode.c
g++ -pg mycode.cpp

These are not all flags, there are many many more. But I have covered most important ones. And I will add, if I find some other important flag. Enjoy!

Further reading : man page of gcc, optimize options

Posted in Programming | Tagged , | Leave a comment

Edit Distance using Dynamic Programming

Edit Distance is quite a interesting and popular problem. Here I present an efficient bottom up C++ program to solve it.

Problem – We are given 2 strings. We have to find the “edit distance” or the cost of converting one string to other. We are allowed 3 operations – Insert, Delete, Replace. All 3 have equal cost that is 1 unit.

Example – Edit distance between “abc” and “abd” is 1. We replaced “c” with “d”. You can also see this as “Delete c”, then “Insert d” which would give a edit distance of 2. But since we try to minimize edit distance, we consider it as single operation that is Replace. Few more examples-
EditDistance(“ab”, “bc”) = 2
EditDistance(“man”, “woman”) = 2
EditDistance(“c”, “java”) = 4
EditDistance(“abcd”, “acd”) = 2

One of the above 4 examples has wrong answer! Tell me in comments which one is wrong,  and what is the correct answer ;)

We will use bottom up version of dynamic programming, as it is much cleaner and efficient (than top down). If the strings have length N and M, we will need a table of size (N+1)*(M+1). First we need to initialize the top row i.e TABLE[0][i] = i and first column i.e TABLE[i][0] = i. These are the base cases in which one of the string is empty. Now filling the rest of the TABLE column wise is simple-

TABLE[i][j] = min(
TABLE[i][j-1]+1,
TABLE[i-1][j]+1,
TABLE[i-1][j-1]+cost,
)
Here cost = 0 if STR1[i] = STR2[j], 1 if unequal

And the C++ function-

int EditDistance(string word1, string word2)
{
    int i, j, l1, l2, m;
    l1 = word1.length();
    l2 = word2.length();
    vector< vector<int> > t(l1 + 1, vector<int>(l2 + 1));

    for (i = 0; i <= l1; i++)
        t[i][0] = i;
    for (i = 1; i <= l2; i++)
        t[0][i] = i;

    for (i = 1; i <= l1; i++)
    {
        for (j = 1; j <= l2; j++)
        {
            m = min(t[i-1][j], t[i][j-1]) + 1;
            t[i][j] = min(m, t[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1));
        }
    }
    return t[l1][l2];
}

The TABLE for “money” and “monkey” looks like->

TABLE

1 is the final answer.

Posted in Algorithm, Programming | Tagged , | 7 Comments

Merge Sort program in C

It is rather amazing, that many programmers are unable to write ‘Merge Sort’ correctly. With its guarantee of O(n log n) time complexity, it is a dependable sorting algorithm. Also it can be used to count number of inversions in a array of integers. Most importantly it is very easy to code! :)

So here is my implementation, of merge sort in C language -

/* 
 *We need 2 arrays 'a' and 'b', of equal size
 *Here 'a' is the primary array (i.e which contains initial 
     input, and final output)
 *And 'b' is the temporary array,
     used for merging 2 sorted half's in 'a' 
 */
 
void merge(int a[], int low, int mid, int high)
{
    int b[10000];
    int i = low, j = mid + 1, k = 0;
 
    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];
 
    while (j <= high)
        b[k++] = a[j++];
 
    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}
 
void mergesort(int a[], int low, int high)
{
    if (low < high) {
        int m = (high + low)/2;
        mergesort(a, low, m);
        mergesort(a, m + 1, high);
        merge(a, low, m, high);
    }
}
Posted in Programming | Tagged , , | 15 Comments

Fastest way to compute Fibonacci Number

While we all know that matrix exponentiation is asymptotically fastest way to compute NthFibonacci number, there is a still faster way-

If we know F(k) and F(k+1), then we can find

F(2k) = F(k)[2F(k+1) – F(k)]
F(2k+1) = F(k+1)2 + F(k)2

This is fast doubling. Here is my python implementation-

#Fast Fibonnaci
def fib(n):
    if n <= 2:
        return 1
    k = n/2
    a = fib(k + 1)
    b = fib(k)
    if n % 2 == 1:
        return a*a + b*b
    else:
        return b*(2*a - b)

if __name__ == "__main__":
    n = int(raw_input("Enter n(0 to quit) : "))
    while n:
        print fib(n)
        n = int(raw_input("Enter n(0 to quit) : "))

Note: I have taken the sequence as 1, 1, 2, 3… However some people consider the sequence as 0, 1, 1, 2, 3…

Posted in Programming | Tagged | 2 Comments