1.1   Algorithms Are Everywhere¶

When we hear the term "algorithm," we naturally think of mathematics. However, many algorithms do not involve complex mathematics but rely more on basic logic, which can be seen everywhere in our daily lives.

Before we formally explore algorithms, here's an interesting fact worth sharing: you have already learned many algorithms without realizing it, and you are used to applying them in daily life. Let me give a few specific examples to illustrate this point.

Example 1: Looking Up a Dictionary. In an English dictionary, words are listed alphabetically. Assuming we're searching for a word that starts with the letter \(r\), this is typically done in the following way:

1. Open the dictionary to about halfway and check the first word on that page; suppose it starts with the letter \(m\).
2. Since \(r\) comes after \(m\) in the alphabet, the first half can be ignored and the search space is narrowed down to the second half.
3. Repeat steps 1. and 2. until you find the page where the word starts with \(r\).

Figure 1-1   Process of looking up a dictionary

Looking up a dictionary, an essential skill for elementary school students is actually the famous "Binary Search" algorithm. From a data structure perspective, we can consider the dictionary as a sorted "array"; from an algorithmic perspective, the series of actions taken to look up a word in the dictionary can be viewed as the algorithm "Binary Search."

Example 2: Organizing Playing Cards. When playing cards, we need to arrange the cards in our hands in ascending order, as shown in the following process.

1. Divide the playing cards into "ordered" and "unordered" sections, assuming initially the leftmost card is already in order.
2. Take out a card from the unordered section and insert it into the correct position in the ordered section; after this, the leftmost two cards are in order.
3. Repeat step 2 until all cards are in order.

Figure 1-2   Process of sorting a deck of cards

The above method of organizing playing cards is essentially the "Insertion Sort" algorithm, which is very efficient for small datasets. Many programming languages' built-in sorting implementations use insertion sort internally.

Example 3: Making Change. Assume making a purchase of \(69\) at a supermarket. If you give the cashier \(100\), they will need to provide you with \(31\) in change. This process can be clearly understood as illustrated in Figure 1-3.

1. The available denominations smaller than \(31\) are \(1\), \(5\), \(10\), and \(20\).
2. Take out the largest \(20\) from the options, leaving \(31 - 20 = 11\).
3. Take out the largest \(10\) from the remaining options, leaving \(11 - 10 = 1\).
4. Take out the largest \(1\) from the remaining options, leaving \(1 - 1 = 0\).
5. Complete change-making, the solution is \(20 + 10 + 1 = 31\).

Figure 1-3   Process of making change

In the steps above, we choose what seems to be the best option at each stage by using the largest denomination available, which leads to an effective way to make change. From a data structures and algorithms perspective, this approach is known as a "Greedy" algorithm.

From cooking a meal to interstellar travel, almost all problem-solving involves algorithms. The advent of computers allows us to store data structures in memory and write code to call the CPU and GPU to execute algorithms. In this way, we can transfer real-life problems to computers and solve various complex issues in a more efficient way.

Feel free to drop your insights, questions or suggestions