Chapter 1

Exercise 1.1-1

In macOS's Finder (sort of file explorer), I frequently list files and folders ordered by name to quickly locate items. Similarly, in a navigation app, I typically select the shortest route, especially for walking tours.

Exercise 1.1-2

For example, space usage, communication bandwidth, energy consumption, etc. There is a need to balance various quality attributes, since not all of them can be simultaneously attained. Most often they are opposing each other. Usually, speed can be improved at the expense of more memory utilization and/or power consumption. Therefore, we need multiple measures of efficiency when describing algorithms.

Exercise 1.1-3

The most basic one is an array that allows accessing elements by index (direct addressing) in constant time. It comes in two flavors: fixed size (like, the built-in C++ or Java arrays) and resizable (like, Python's list or Java's java.util.ArrayList). Insertions and removals of elements at arbitrary positions are, on average, linear in number of elements. Searching for element by value in an unsorted array takes linear time, too. If elements are sorted, then binary search can be used in logarithmic time. Unfortunately, it is not possible to maintain this sorted order in logarithmic time in case of updates.

Exercise 1.1-4

Both problems focus on optimal routes in graphs. The shortest-path problem, finding the minimum distance between two vertices, is efficiently solvable. Conversely, the traveling-salesperson problem, finding the shortest route connecting all vertices, is NP-complete and requires approximate solutions.

Exercise 1.1-5

Classical answers about best solutions revolve around life-critical software systems, like, traffic collision avoidance system or using treatment planning software in a radiation therapy process. The rationale is that any error is prohibitive. Nonetheless, there is a totally different perspective nothing to do with criticality of a software system.

In solved games like tic-tac-toe, a program must play perfectly against a knowledgable opponent, using only the best moves. However, in games like chess or go, moves are based on heuristics and can't be proven as the best. Therefore, if a good enough move works, it might be considered the best.

Genuinely complex systems exhibit emergent properties, thus making predictions about optimal solutions nearly impossible. For more information, consider watching the course Understanding Complexity.

Exercise 1.1-6

An example is a navigation application that uses external sources to acquire real-time traffic information. At the start of a journey, the system calculates an itinerary based on static data. During the trip, there might be changes to the original plan due to unforeseen events such as heavy congestion, traffic accidents, or road works. The system cannot predict whether an alternative route will encounter further issues, and therefore must make decisions based on the current state of traffic conditions.

Exercise 1.2-1

A recommender system for eCommerce sites uses algorithms like content-based and collaborative filtering. They recommend products based on shopping history, viewed items, and user preferences.

Exercise 1.2-2

For solving numerical problems you may leverage a mathematical tool, like WolframAlpha (see Problem 1-1 how to setup a numerical task).

$2 \leq n \leq 43$

Observe that there is nothing to sort when $n=1$.

Exercise 1.2-3

$n=15$

Problem 1-1

The table is filled assuming 30 days per month and 365 days per year. Each entry is a solution of the equation $f(n)10^{-6}=t$. Suppose that you want to solve $n!*10^{-6}=60*60*24$, which determines the largest size of $n$ of a problem that can be solved in 1 day, assuming that the algorithm to solve the problem takes $n!$ microseconds. Execute the next statement in WolframAlpha: solve n! * Power[10,-6] = 60 * 60 * 24 for real n It will report n ≈ 13.9966, so simply take 13 after dropping the fractional part.

You can fill out the entire table using Wolfram Cloud, where you can run scripts written in the Wolfram language. WolframAlpha is suitable for single queries.

For instance, a cubic algorithm can solve the same size problem in a fraction of a second, while a factorial algorithm might take centuries. No hardware or distributed system can match the efficiency gained by switching to better algorithms. This is why algorithms are regarded as technology.

	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
$\lg n$	$2^{10^6}$	$2^{6\cdot10^7}$	$2^{3.6\cdot10^9}$	$2^{8.64\cdot10^{10}}$	$2^{2.592\cdot10^{12}}$	$≈2^{3.1\cdot10^{13}}$	$≈2^{3.1\cdot10^{15}}$
$\sqrt n$	$10^{12}$	$3.6\cdot10^{15}$	$≈1.3\cdot10^{19}$	$≈7.5\cdot10^{21}$	$≈6.7\cdot10^{24}$	$≈9.95\cdot10^{26}$	$≈9.95\cdot10^{30}$
$n$	$10^6$	$6\cdot10^7$	$3.6\cdot10^9$	$8.64\cdot10^{10}$	$2.592\cdot10^{12}$	$≈3.1\cdot10^{13}$	$≈3.1\cdot10^{15}$
$n\lg n$	62746	$≈2.8\cdot10^{6}$	$≈1.3\cdot10^{8}$	$≈2.8\cdot10^{9}$	$≈7.2\cdot10^{10}$	$≈7.98\cdot10^{11}$	$≈6.9\cdot10^{13}$
$n^2$	1000	7745	60000	293938	$≈1.6\cdot10^6$	$≈5.6\cdot10^6$	$≈5.6\cdot10^7$
$n^3$	100	391	1532	4420	13736	31593	146645
$2^n$	19	25	31	36	41	44	51
$n!$	9	11	12	13	15	16	17