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.

2 comments :

  1. 2n/8-n<0 from this how to do i get the next line i.e. value of n?
    2≤n≤43

    ReplyDelete