Chapter 1 Section 2 Exercises Intro to Algorithms CLRS (3)

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: Any application which seeks an optimized output (efficient paths for example).

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 64nlgn steps. For which values of n does insertion sort beat merge sort? Solution: We find where they're equal and note that they're both increasing. 8n^2=64nlgn -> n = 1.1 or n=43.56. These serve as the endpoints of the interval for which insertion sort beats merge sort. In other words, use insertion sort for n<44 (since the n=1 case is trivially sorted).

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 2^n on the same machine? Solution: Solve for the points of intersection as in 1.2-2 to find n=0.1 or n=14.3. This makes sense since if n=0, 0<1, but 100n^2 grows quickly on small positive values until 14.3, when the values are then dominated by 2^n.

Introduction to Algorithms, 3rd

Cormen, Leiserson, Rivest, Stein

1.2 Exercises