Author Archives: vinayakgarg

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. So what would be the output? In what order … Continue reading

Posted in Programming | Tagged , , | Leave a comment

String’s length

Originally posted on Andrzej's C++ blog:
Let’s start with a small test. Is the following assertion correct? void test_length(std::string const& s) { assert(s.length() == strlen(s.c_str())); } It is not; otherwise I wouldn’t be mentioning this in the post; but…

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 So every time you run the program, you get new set of random numbers. Do you see the problem? … Continue reading

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 … Continue reading

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 … Continue reading

Posted in Algorithm, Programming | Tagged , | 10 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 an array … Continue reading

Posted in Programming | Tagged , , | 27 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 … Continue reading

Posted in Programming | Tagged | 8 Comments