# Book Notes: Algorithm to Live By

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**.