## 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.

Here, we need to determine the value of n such that 8n

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:

Answer: 2 <= n < 44.

Here, we need to determine the smallest value of n such that 100n2 < 2n. The value of n evaluates to

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

**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 8n**^{2}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 8n

^{2}= 64nlgnFor 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 100n**^{2}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

Labels:
algorithms,
C/C++,
programming

Bookmark this post:blogger tutorials
Social Bookmarking Blogger Widget |

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

2012-04-29T20:51:00+05:45

Cool Samar

algorithms|C/C++|programming|

Subscribe to:
Post Comments (Atom)