December 09, 2019

Chapter 1 — The Role of Algorithms in Computing

1.1 Algorithms

1.1-1

The convex hull problem may be applied to objects with complex shapes like cars and drones in order to produce a simple shape that can be used in collision avoidance algorithms.

1.1-2

There are other measures of efficiency, besides speed, that may be used in the real-world. For example, space (memory and hard-disk), energy consumption, lines-of-code.

1.1-3

Arrays are good at recalling elements at a particular index. Inserting or deleting elements is usually not possible unless it is a dynamic array and usually involves reallocating memory or copying the elements to a new array.

1.1-4

In both the shortest-path and traveling salesman problems we’re trying to minimize the distance. However, in the traveling salesman problem we have the extra restriction of having to visit every point in the network whereas the shortest-path problem only requires the start and goal nodes to be visited (along with any node along the shortest path).

1.1-5

With most sorting applications (e.g., prioritization, alphabetization), only the best solution will do. In mail delivery services, which encounter the traveling salesman problem every day, approximate solutions must be found to operate the business effectively.

1.2 Algorithms as a technology

1.2-1

Applications that determine map routes rely on shortest path algorithms. These algorithms must be able to handle very large networks and variable constraints.

1.2-2

Suppose we are comparing implementation 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?

$1.1 < n < 43.559$

1.2-3

What is the smallest value of n such that an algorithm whose running time is $100n^2$ is faster than an algorithm whose running time is $2^n$ on the same machine?

For $100n^2$, the running time is 19,600 for $n = 14$ and 22,500 for $n = 15$. For $2^n$, the running time is 16,384 for $n = 14$ and 32,768 for $n = 15$. Therefore, the answer is 15.

Problems

1-1 Comparison of running times

For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
$\lg n$	$2^{10^6}$	$2^{6 \cdot 10^7}$	$2^{36 \cdot 10^8}$	$2^{864 \cdot 10^8}$	$2^{2592 \cdot 10^9}$	$2^{31536 \cdot 10^9}$	$2^{3155760 \cdot 10^9}$
$\sqrt{n}$	$10^{12}$	$36 \cdot 10^{14}$	$1296 \cdot 10^{16}$	$746496 \cdot 10^{16}$	$6718464 \cdot 10^{18}$	$994519296 \cdot 10^{18}$	$9958821177600 \cdot 10^{18}$
$n$	$10^6$	$6 \cdot 10^7$	$36 \cdot 10^8$	$864 \cdot 10^8$	$2592 \cdot 10^9$	$31536 \cdot 10^9$	$3155760 \cdot 10^9$
$n \lg n$	62746	2801417	133378058	2755147513	71870856404	797633893349	68656519951424
$n^2$	1000	7745	60000	293938	1609968	5615692	56176151
$n^3$	100	391	1532	4420	13736	31593	146679
$2^n$	19	25	31	36	41	44	51
$n!$	9	11	12	13	15	16	17

	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
\(\lg n\)	\(2^{10^6}\)	\(2^{6 \cdot 10^7}\)	\(2^{36 \cdot 10^8}\)	\(2^{864 \cdot 10^8}\)	\(2^{2592 \cdot 10^9}\)	\(2^{31536 \cdot 10^9}\)	\(2^{3155760 \cdot 10^9}\)
\(\sqrt{n}\)	\(10^{12}\)	\(36 \cdot 10^{14}\)	\(1296 \cdot 10^{16}\)	\(746496 \cdot 10^{16}\)	\(6718464 \cdot 10^{18}\)	\(994519296 \cdot 10^{18}\)	\(9958821177600 \cdot 10^{18}\)
\(n\)	\(10^6\)	\(6 \cdot 10^7\)	\(36 \cdot 10^8\)	\(864 \cdot 10^8\)	\(2592 \cdot 10^9\)	\(31536 \cdot 10^9\)	\(3155760 \cdot 10^9\)
\(n \lg n\)	62746	2801417	133378058	2755147513	71870856404	797633893349	68656519951424
\(n^2\)	1000	7745	60000	293938	1609968	5615692	56176151
\(n^3\)	100	391	1532	4420	13736	31593	146679
\(2^n\)	19	25	31	36	41	44	51
\(n!\)	9	11	12	13	15	16	17