# Algorithms to live by

Optimal stopping problem. Aka the secretary problem.

Time to a search if unbounded. If number of candidates is fixed. If no incomplete information, observation only, then 37% is optimal. If full information, score and only that score matters. Never hire unless it's the best you've seen so far, 58%.

Selling a house, know objective dollar value, and rough range. Not single best, most money, waiting has a cost. Set one going in, take first option to exceed it.

Explore vs Exploit.

Always exploring can be frustrating. Multi-armed bandit problem and casino's. Time is the key value, exploring goes down over time, exploit goes up. Need to discount payoffs based on time. You care more about the meal tonight than the one a month from now, geometrically discounting. Giddens Index. If you don't have time, think about regret. Total amount of regret will always increase, minimize regret. Regret Minimization Algorithms. Upper Confidence Bound. Choose the one with the highest confidence bound, it's always greater than the expected value. Optimism fights against regret. High value of the 0/0 (try/win) option. Win-stay, loose-shift explores too much.

Sorting.

Sometimes sorting isn't worth the time, only if your searching. Fault tolerant sorting, were comparisons have error bars, you want more comparisons like bubble or counting sort. In animal pecking order, sorting helps against larger amounts of antagonizing. Cardinal ordering like races allow for O(n) to sort.

Caching.

LRU is most efficient,along many axes such as geography.

Ebbinghouse forgetfulness curve, Brain has unlimited storage, limiting factor for is time. This is also how society organizes information.

More memory is slower, interesting collelary with age. Maybe older people are slower because they have to search though more stuff.

Scheduling.

Inputs/goals are usually due date, number of workers, throughout or latency. Look from outsiders perspective, sun of completion time, or shortest thing first, can also weight these and divide duration by weight. Procrastination is like DDOS, doing lots of small things of low weight.

Weighted shortest processing time with preemption is most efficient in general.

Thrashing and context switching. Be “less smart” in how much you can do. Just force a lower limit on responsiveness, like the tomato timer. Great analogy for email.

Bayes Rule.

LaPlass and Bayes. Chances of event are W+1/N+2.

Look at the distribution for those events, predict accordingly. for a power law, if you’re past a certain point the longer you can expect it to go. Multiplicative, average, additive for the Power law, standard, Erlang distributions.

Overfitting. Better fit for existing data but not necessarily for future data (predictions).

Incentives cause over fitting, the model forces behavior. Lasso effect reduces factors, brain may do something similar, with fewest neurons to get job done.

Minimax, minimize maximum regret.

More time to analyze can also cause over fitting, too much data or detail. The delta between what is measurable and what matters, the greater the better the simplicity. For example the further ahead you need to brainstorm the thicker pen you use.

Optimization problems. "Perfect thanks is the enemy of good" -voltaire

Just relax. Constraint relaxation. Allows for you to find the lower bound of a problem. For example minimum spanning tree and the TSP. Continuous relaxation, Lagrange approach for discreet optimization problem. Constraint relaxation, continuous relaxation, Lagrange based penalty relaxation.

Randomness. Montecarlo method of randomly sampling. Key part of scientific discovery, randomness, serendipity.

Hill climbing, use randomness to get out of local maxima. Metropolis, following error inversly proportional to how far off it is. Simulated annealing, front load randomness and cool off more over time.

Networking. Packet switching vs circuit switching. Exponential back off allows for finite patience and infinite mercy. AIMD for flow control, and use this. Pushing to breaking point, quick failure mode. Peter principle, ever employee will be promoted until they are not incompetent, perhaps model orgs like this.

Feedback, acks in a network, happen in human communication as well, even one way comms. Buffers only work well if they are continuously cleared out. In the internet age we suffer from buffer bloat, need to drop packets.. happens naturally in physical world.