Book Notes: Algorithm to Live By

Amudi Sebastian -

I want to start sharing raw notes of interesting books I read.

I highly recommend this book, a lot of interesting insights. How I take notes might not make sense to most people. I take notes of keywords and interesting headlines. I'd deep dive into the keyword if I need to go back and learn more about it.

My favorite chapters are the first (Optimal Stopping) and the last (Game Theory).

Optimal Stopping

  • 37%

Explore/exploit

  • Multi-armed bandit problem
  • A/B testing.

Sorting

  • Linearithmic (n log n).
  • Bucket sort.
  • Sort is prophylaxis to search.
  • Noisy comparison.

Caching

  • Eviction algo: FIFO, LRU.

Scheduling

  • Shortest task first.
  • Single-machine scheduling.
  • Due date - maximum lateness.
  • Earliest due date.
  • Moore's algorithm.
  • The sum of completion time, and shortest processing time.
  • Weighted completion time.
  • DoS attack.
  • Priority inversion - priority inheritance, precedent constraint.
  • Intractable.
  • Pre-emptive and uncertainty.
  • Thrashing.
  • Interrupt coalescing.

Bayes' Rule

  • Multiply prior probabilities.
  • Predict future probabilities.
  • Lifespans.
  • Kapernican principle.
  • Richer prior information - better prediction.
  • Gaussian distribution/bell curve.
  • Power law distribution / scale-free distribution.
  • Good instinct when each distribution applies.
  • Erlang distribution - predict a constant time longer.
  • Prediction rule: multiplicative, average, additive.
  • Small data is big data in disguise.
  • Protect good priors.

Overfitting

  • Moral algebra.
  • Deliberately thinking less.
  • Try to explain the past and predict the future.
  • Idolatry of data.
  • Incentive structure in business - the company builds whatever the CEO decides to build.
  • Detecting overfitting: cross-validation.
  • Involve less data.
  • Regularization.- penalty for complexity.
  • The lasso.
  • Early stopping.
  • When to stop? Broad strokes vs fine lines.
  • Use judgment.

Relaxation

  • Traveling salesman problem.
  • Minimum spanning tree as starting point to find an optimal solution.
  • Solve a simplified version of the problem to find a starting point for a solution to the real problem.
  • Continuous relaxation.
  • Lagrangian relaxation, put a cost to breaking constraints in discreet problems - softening hard constraints.

Randomness

  • Good approximate answer faster.
  • Need to know when, in what way, and to what extent.
  • Sampling.
  • Monte Carlo method.
  • How to find prime numbers - cryptography.
  • False positive - witness against primality.
  • Miller-Rabin Test.
  • Polynomial identity testing.
  • Veil of ignorance.
  • Bloom filter - check URLs for malicious sites - uniqueness witness check.
  • Greedy, hill-climbing algorithms, shutdown hill-climbing, metropolis algorithm - avoid local maxima.
  • Annealing - how quickly or slowly a material cooled.
  • Simulated annealing.

Networking

  • TCP.
  • Packet switching.
  • Two generals problem.
  • Triple-handshake.
  • ACKs package.
  • Set period of non-responsiveness.
  • Exponential back-off.
  • Aloha-net.
  • Flow control & Congestion avoidance.
  • Full/slow meta-communicate how fast packages should be sent.
  • AIMD.
  • Ant colony has this too.
  • Any employees tend to rise to their level of incompetence.
  • Up or out policy.
  • Manage capacity.
  • Dynamic hierarchy in the company.
  • Back channels - ACKs and feedback/nods.
  • Buffer bloat - ack packages get stuck in the buffer.
  • Tail drop - packages get deleted.
  • Explicit congestion notification ECN.
  • Consider time as a first-class citizen.

Game Theory

  • Recursion.
  • Anticipate others' opinions.
  • Leveling. Play 1 level above your opponent. Use game theory to break recursion.
  • Equilibrium.
  • John Nash - Nobel prize, Nash Equilibrium - always exists in 2 players' games.
  • Truth - math, complexity - computer science.
  • Algorithmic game theory - find Nash equilibrium.
  • The prisoners' dilemma.
  • Dominant strategy.
  • The price of anarchy - maximize the outcome for an individual.
  • Selfish routing in network - low price of anarchy.
  • Anarchy is 4/3 worse than the ideal cooperative solution.
  • Unlimited vacation game theory.
  • Mechanism design / reverse game theory - worsening the unsatisfactory equilibrium. Example: stock market closed.
  • Cooperation - emotions.
  • Auctions.
    • Sealed bid first price auction.
    • Dutch auction / descending auction.
    • English / ascending auction.
    • Vickrey auction - sealed bid second price - strategy-proof.
  • Revelation principle.

Conclusion: Computational kindness.