## Thursday, 16 March 2017

### Chapter 1 Exercise 1.2, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

Solution:

Maps are one of the application which requires algorithmic content. One of the basic and widely used algorithm is the shortest path finder between 2 points.

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 64n.lg(n) steps. For which values of n does insertion sort beat merge sort?

Solution:

Solving the simple equation:

8n2 <64n.lg(n)
n<8.lg(n) (dividing both sides by 8n)
n/8<lg(n) (dividing both sides by 8)
2n/8<n
2n/8-n<0
2≤n≤43

Insertion sort is faster for range [2 to 43].

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?

Solution:

100n2< 2n

 n 100n2 2n 1 100 2 5 2500 32 10 10000 1024 14 19600 16384 15 22500 32768

For n>14 the 100n2 runs faster than 2n.