Algorithms to Live By

After listening to the 80,000 hours podcast episode 48 I realized that this book was right up my alley and decided it was worth a book review awhile ago but never put it together until now.

Key Concepts and Algorithms:

1. Optimal Stopping – The Secretary Problem.

2. Optimal Stopping with full information (Threshold rule). Set a threshold and anyone over that threshold.

3. Multi-Armed Bandit Problem.

4. Regret Minimization Framework (upper confidence bound).

5. A/B Testing.

6. Adaptive Trials.

7. Time Complexity Analysis:

   Worst case: O(Of a thing)

   Average Case: Θ(Of a thing)

   Best Case: Ω(Of a thing)

8. Err on the side of messiness

9. Caching: Lots exist but here are some easy ones I like.

   a) First in first out (FIFO)

   b) Last in first out (LIFO)

   c) Least recently used (LRU)

10. Minimizing Maximum Lateness.

11. Moore’s Algorithm: the official “oh shit, that’s due super soon” algorithm.

12. Thrashing, how do I remove it as an issue.

13. Interrupt Coalescing: batching related tasks into a specific timeframe.

14. Response-Time vs Throughput: being available for stuff vs getting stuff done.

15. Overfitting, Cross Validation.

16. The traveling salesman problem.

17. Constraint Relaxation.

18. Computational Kindness

    Ask for meetings, appointments, etc. at specific times. Adding constraints to problems helps elimination ambiguity.

    Say your preferences instead being “open to whatever.”