Predicting the Future Everyone claims they can’t predict the future. But mathematically, we can do better than guessing. The real problem isn’t the lack of predictive tools, it’s that most people never learned to use them. Let’s say we’re trying to predict if it’ll rain tomorrow. Last year, during this same month it rained 5 out of 30 days. A simple way to calculate the probability is by dividing the rainy days by the non-rain days: ...
Scheduling is an interesting optimization problem that we encounter every day. You schedule things like brushing your teeth, driving to work, and eating a meal, whether consciously or subconsciously. I’m sure most people (me included) don’t care to fully optimize their personal schedule in favor of adding a buffer between tasks. Someone who is trying to optimize their schedule is in for a monumental task. This type of scheduling problem is similar to an NP-hard problem in computer science, sometimes called the “Job-Shop Scheduling” problem. NP-hard problems are problems in which new inputs increase complexity combinatorially. In other words, adding a new task to your schedule would greatly increase the time required to fully optimize it. And that is the key piece of information here: fully optimize. What benefit do you actually get from having the most streamlined schedule if you have to schedule 2 hours a day optimizing your schedule tomorrow? ...
Caching involves storing frequently accessed data in a temporary storage location to improve performance and reduce the need to access slower storage systems. Deciding when to evict items from the cache when it reaches capacity is a key challenge. If important items are removed, performance can degrade. Some common cache eviction strategies are: Least Recently Used (LRU): Removes items accessed the longest time ago. Least Frequently Used (LFU): Removes items that have been accessed the least number of times. First in First Out (FIFO): Removes the items added the longest time ago. As a real-world example, a library “caches” books at the front that are frequently requested, so that patrons can access them quickly without having to wait for the book to be retrieved from the shelves. ...
The third chapter of Algorithms to Live By is about sorting. Some examples of sorting you might encounter: Ordering books on a shelf (if you still have physical ones) Participating in a tournament orders individuals/teams by skill (with varying degrees of reliability) Sorting food in your fridge so you know where to look for things With more digitization these days, computers will handle most of the mundane sorting like ordering documents, but it’s interesting to realize how we naturally follow some of these algorithms. Let’s take an example of ordering your todo list by priority: ...
The explore exploit chapter in the book “Algorithms to Live By” looks into the problem called the “Multi-armed Bandit”. The “Multi-armed Bandit” is when you have multiple independent choices with different reward probabilities, and you can only try one at a time (like a slot machine). One algorithm that the book describes to tackle this problem is the Gittins Index. The Gittins Index is a fairly complicated calculation, but the idea for the slot machines example is that it favors exploration of new machines when there is less data gathered about the odds. The amount that the index favors exploration is calculated from the “discount” factor, the higher the discount factor, the more exploration. For example, if you only have a few minutes to test the machines, then you might choose a lower discount factor, because you don’t have time to test any one thoroughly, so stick with a decent one if you find it. With a high 90% factor, shown in the graph below, even a machine with a 9 to 5 win ratio would have a lower Gittins Index than an untested machine, guiding the player to move on. ...