Algorithms & Our Daily Life
Computers are not the only ones following algorithms, but humans also do so in ways that are often overlooked. Algorithms to Live By is one book that correlates 11 different Computer Science algorithms with our daily lives.
In this blog, I will be discussing some of the key things that I remember from the book:
Optimal Stopping: Our dilemma is not which option to consider, but how many options should we even consider before making a decision or setting a baseline. The answer to this dilemma can be found in the Secretary Problem. Let's say you want to hire a secretary. You will have to interview candidates for that, and once you reject someone, you cannot contact them again, once you have selected someone, the process ends.
The question in the above problem is how to maximize the chances of selecting the most suitable candidate. We cannot stop early because we leave the most promising applications uncovered and also because we do not have a baseline set. Again, stopping late is not an option since we might be waiting for a candidate who does not exist. Finding the optimal point between the two is the key to finding the optimal strategy, which comes out to be
37% or 1/e. In other words, we interview & reject the first few candidates we come across, regardless of how qualified they are. Once the baseline is established, we hire the next one better than anyone we have seen so far. There are also variations of the Secretary Problem that can be applied to parking, dating, and selling and buying houses.
Caching: When space is limited, caching is a smart way to save time and money. Among the most common techniques are Random Eviction, First-In-First-Out, and Least Recently Used. Using LRU, we can turn the library inside out by creating a separate cache section for books that have been recently returned. This is because those are the books that are likely to be borrowed again. Caching also includes documentation, which can be explained by the Forgetting Curve. Documentation can help humans retain what they have learned, as they tend to forget stuff over time.
A cache's proximity is just as useful as its cache itself. Most Internet traffic today is handled by Content Delivery Networks (CDN), which maintain copies of data so the user can request a page from a nearby computer, thereby speeding up the response time.
Explore/Exploit: This algorithm attempts to answer the question of whether we should try new things or stick to what we know. Which is better, a new restaurant or one we have already visited? The Multi-Arm Bandit Problem can be used to resolve this dilemma. In a casino slot machine, we keep pulling an arm as long as it pays off, according to this strategy. We switch to another arm if a particular pull doesn't pay off.
A/B Testing is another example of the Explore/Exploit Trade-off. A company creates several different versions of the webpage (Explore) and makes it available in limited availability to know which has the most clicks/usage from the end-users. Once they know which version works best, they make it available to all users (Exploit). This concept can also be applied to clinical trials.
Scheduling: The main idea behind schedule is to get things done. There are two ways to handle this: 1) Earliest Due Date: In this case, we start with tasks due soonest & then go to that task due last. It aims at minimizing lateness. 2) Shortest Processing Time: Here, the aim is to minimize the sum of completion time, hence we pick up things that take less time & then proceed with time-consuming tasks. The chapter also mentions commonly known problems like Thrashing & Priority Inversion.
I think that the concept of scheduling can also be related to the use of Jira Software. Which issue/task is to be picked up next depends either on the priority of the issue (Earliest Due Date) or the story points allocated to the issue (Shortest Processing Time). In scenarios where some important bug that a customer is facing is assigned to us, there is priority inversion as the new incoming task gets higher priority.
Sorting: We come across sorting while we check our emails, browse for restaurants, and check our Facebook/Instagram feeds. The content is sorted based on the requirements presented by the user. When we search for something on Google, it sorts the various web pages to show us the relevant ones. One interesting thing that this chapter mention is the tradeoff between sorting & searching where it states that Sorting something that you will never search is a complete waste, searching something you never sorted is merely inefficient.
Google sorts the web pages since the cost of sorting is very less compared to searching & the data will be searched for repeatedly. The sorting is performed by machines ahead of time so that end-users can experience faster results. On the other hand, sorting your bookshelf at home is not that important as ordering the books will take more time and energy than scanning through them.
Did you find this article valuable?
Support Shloka Shah by becoming a sponsor. Any amount is appreciated!