Sunday 29 April 2012

Answers To Introduction To Algorithms 1.2-2 and 1.2-3

Algorithm is a fun subject and we are starting from the very basics of algorithm. Here is my solution for selected questions from chapter 1 of Introduction To Algorithms by Cormen and others.

1.2-2) Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlg n steps. For which values of n does insertion sort beat merge sort?

Here, we need to determine the value of n such that 8n2 = 64nlgn

For the value n = 1, obviously the merge sort beats the insertion sort so we will start from 2 and find the higher limit up to which the insertion sort beats merge sort.

The above equation can be further reduced as n = 8lgn. We can now solve it to determine the value of n. A simple code in C that would do the job for us is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int merge = 8 * log2(i);
  if (i > merge)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

Answer: 2 <= n < 44. 1.2-3) What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

Here, we need to determine the smallest value of n such that 100n2 < 2n. The value of n evaluates to 15. The source code for above problem is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int x = 100 * pow(i, 2);
  int y = pow(2,i);
  if (x < y)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

I hope this helps some of the algo beginners out there trying to solve the questions from "Introduction To Algorithms". Btw, they are basic maths however :P