Algorithms to Live By: The Computer Science of Human Decisions

This section introduces the concept of optimal stopping problems, illustrating the challenge of deciding when to commit in scenarios with limited, irreversible options. The 37% rule suggests exploring 37% of opportunities to establish a baseline, then choosing the first option that surpasses everything previously encountered. This strategy balances information gathering with timely commitment in various life decisions.

The explore/exploit tradeoff examines the dilemma between trying new things (exploration) and sticking with known preferences (exploitation). This balance is crucial for a fulfilling life and depends on the remaining time in a given interval. Modeled by the multi-armed bandit problem, decisions must consider the long-term sequence, valuing exploration more when there's more time to benefit.

Sorting is a fundamental operation in computing and daily life, essential for organizing information from email inboxes to search results. Despite its importance, sorting is prone to diseconomies of scale, meaning unit costs rise with item quantity. Efficient algorithms like Mergesort (divide-and-conquer) and Bucket Sort (using prior knowledge) break the quadratic barrier, while Big-O notation evaluates worst-case performance.

Caching involves managing memory hierarchies to balance speed and capacity by keeping frequently accessed information in easily accessible locations. The Least Recently Used (LRU) policy is a common and effective heuristic, assuming recently used items will be needed again. This principle applies to computer systems, library organization, and even domestic filing, demonstrating that forgetting can be an optimal tuning to environmental needs.

Scheduling optimizes tasks by choosing the correct metric for success. Strategies like Earliest Due Date minimize lateness, while Shortest Processing Time clears to-do lists quickly, especially when weighted by importance. Issues like priority inversion and precedence constraints make most scheduling problems intractable. Preemption and interrupt coalescing are strategies to manage uncertainty and context switching costs.

Bayes's Rule provides a framework for predicting the future from small data by reasoning backward from evidence and updating prior beliefs. Laplace’s Law offers a simple formula for estimating probabilities, while the Copernican Principle forecasts durations based on current age. Understanding normal vs. power-law distributions is crucial for accurate predictions in various real-world phenomena.

Overfitting occurs when a model becomes too complex, perfectly fitting past data (including noise) but failing to make accurate future predictions. This highlights the danger of data idolatry and over-reliance on proxy metrics. Strategies like cross-validation detect overfitting, while regularization combats it by penalizing complexity, often leading to better results with simpler heuristics in uncertain environments.

Many real-world problems, like the traveling salesman problem, are computationally intractable, meaning they lack efficient optimal solutions. Relaxation techniques address this by simplifying constraints: constraint relaxation removes rules, continuous relaxation uses fractions, and Lagrangian relaxation turns rules into costs. These methods provide useful approximations and lower bounds, making hard problems manageable.

Randomness is a powerful tool in computer science, offering efficient approximate solutions to difficult problems faster than deterministic methods. Sampling (e.g., Monte Carlo) estimates complex quantities, while randomized algorithms (e.g., Miller-Rabin) test primality. Randomness helps escape local maxima in optimization through techniques like simulated annealing, and is also a cornerstone of evolution and creativity.

Networking relies on protocols for communication, breaking data into packets for robustness (packet switching). Acknowledgment ensures reliability over unreliable channels (Byzantine generals problem). Exponential backoff resolves interference in crowded channels, while flow control (AIMD algorithm) manages congestion. Bufferbloat highlights that latency is often more critical than raw capacity, encouraging strategies like "tactical dropped balls."

Game theory analyzes interactions between multiple agents, involving recursive thinking about others' actions. A Nash equilibrium is a stable state, but finding it can be intractable. The prisoner's dilemma illustrates how individual rationality can lead to collectively worse outcomes. Mechanism design aims to change game rules to encourage desirable behaviors, often through external consequences or evolutionary "internal mechanism designers."

Computational kindness advocates for framing interactions to minimize others' cognitive labor. This means providing clear preferences, limiting options, and designing systems (like linear parking lots or real-time transit displays) that reduce mental strain. By simplifying decision-making and prioritizing social cooperation over exhaustive calculation, algorithmic principles enhance navigating complex daily existence.