1.2 Algorithms as a technology

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.

• Application: Class schedule
• Function: avoid confict that a student has two classes at same time or a student has a class which requires completion one unfinished training course

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

$$ \begin{aligned} 8n^2 < 64n \lg n \cr 0 < n < 8 \lg n \cr 1< 2^n < n^8 \cr 2 \leq n \leq 43 \cr \end{aligned} $$

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?

$$ \begin{aligned} 100n^2 < 2^n \cr n \ge 15.\cr \end{aligned} $$