Review: Algorithms to Live By
Can problems that appear throughout computer science, many of which are well understood and solved, help us in our daily lives? This book demonstrates that there are many applications for solutions outside the technological space.
This following is an affiliated link for amazon.co.uk - if you click it and purchase the book, I will receive a commission. If you do not feel comfortable with this, simply search for the title in your favourite on-line bookstore.
Whether it’s trying to plan the best route to visit ten cities, sorting out your wardrobe for efficiency, deciding who should sit at what tables at a wedding or how to most efficiently clear off the items on your to do list, there are plenty of common tasks that have a corresponding problem in technology.
These problems have been studied so thoroughly that in many cases we can just apply the results, knowing that we would not be able to do any better by taking another strategy. For example, few web developers write sorting algorithms, generally using the development framework's in-built functionality, which should fit all general purposes.
In many cases what is optimal for a computer program can also provide an optimal solution for a practical problem in the real world. Often we choose a solution based on intuition, but is it the optimal way of accomplishing something?
For example, the book opens with optimal stopping, which can be summarised by the Secretary Problem. If you are interviewing candidates to be your secretary one by one, not knowing at what point the most qualified will arrive, and where passing on somebody means they cannot be recalled; what strategy will give you the best chance of getting the most suitable employee?
This problem arose in the 1950s when secretaries may have been the norm. A more contemporary version might be how long should you spend looking at apartments before you make an offer. You want to maximise the chance of getting the right place for the right price, but if you hesitate you might lose the opportunity forever.
The answer depends on how much time is available. Spend thirty seven per cent of the total time allocated to finding an apartment, looking without committing to establish a baseline. After that point, be ready to make any offer that meets the requirements and beats all previous places that you have seen.
This is a simple algorithm to follow and gives the best possible results given the constraints. The probability of success with this optimal strategy, however, is disappointingly low. The chances of getting the best possible apartment is slightly better than one in three, but it’s much better then any other approach. And this has been proved; don't worry, the details of the proof are outside the scope of both the book and this post.
Target Audience
This is a must read for developers or anyone working technical background. The problems should be familiar: sorting, searching, caching, scheduling, game theory, probability and so on. The application to practical everyday tasks and activities from playing poker to waiting for a bus is fascinating.
How often do we apply what we know about these topics and their solutions in technology to how we organise and do things in the real world? There are advantages to doing so in a wide range of activities. It helps to have a basic understanding of the theory, but it is not required to get the most out of the book.
The authors present each topic in a easy to digest format with enough technical detail for those with a background to be satisfied, but not overpowering the practical discussion of the topics. A non-technical person should enjoy the reading of this book, giving them a glimpse into the problems faced by computer scientists, but more importantly insights into how the lead their own lives.
Following reading this book, I’ve changed my approach in a few areas. Here’s what I learned.
Exploiting or Exploring
The concept of exploration versus exploitation is that up to a certain point, trying new things will stop producing rewards compared to making use of the knowledge of the known things. The example used is trying new restaurants. At some point you are going to want to make use out of the information - which restaurants you like - to decide your next meal. Sticking to what you already know makes more sense than trying yet another new restaurant.
Figuring out when to switch is the problem. The answer is that it depends on how long the period that you can exploit what you learned is going to be. For example, on the last night before leaving a city that you've been in for many years, it makes sense to revisit a favourite restaurant, where you have confidence that you will enjoy your meal, rather than to try an unknown and risk disappointment.
This hit a nerve with me and my family this January. We are trying to choose a Summer holiday destination and were considering going back to the same resort in France that we had such a lovely time in last year. But would we miss out on something better?
Our children are both young; we can expect to have many more vacations in the future, not just in summer but around school holidays also. Lets say about ten to twelve more years before our youngsters want to do their own thing.
The book would suggest that in this case it makes sense to stick with the exploration phase for a few more years. Try new things. See what works. After that the whole family will have a better idea of what they want to do. We can switch into an exploit mode and spend the last few years of our holidays together revisiting the best types of holidays.
Scheduling and Priority
Should I work on the task with the closest looming deadline, even though it will take most of the day? Or should I try to clear out the tasks that will be quickest and therefore get more tick marks on my to-do list? This is a choice between Earliest Deadline First or Shortest Time First, and is faced by computers and humans alike.
This problem can be solved to a particular metric, such as reducing the amount of missed deadlines, reducing the overall amount of stuff to do, or reducing the amount of wait time for customers; each strategy will solve a particular problem. Knowing the limits and possibilities of each approach is key to getting the most out of my own day.
The fact that introducing an extra bit of data into the problem, such as placing a priority on different tasks, can change the problem into an intractable one is an eye opener. The authors give a good explanation for Big O Notation; a means for describing how hard a problem is based on the worst case running time for the best solution. It puts in perspective what we should try to achieve in our own lives.
Throw into the mix the need to switch context whenever an interruption occurs or an email, text or phone call breaks the chain of thought. The cost for these are well documented in computer science, caching in particular is an involved science; can we derive any advice from what we know?
What I've tried to take away is to know what metric I want to measure success by. Rather than spend a day completing lots and lots of small unimportant tasks, I want to devote significant time to the difficult, time consuming pieces of work, that I will ultimately be judged upon.
I will always have many pieces of administration to deal with, there will be questions from more junior members of staff and we have to plan our releases and the future features the development team will work on. All important but perhaps not urgent. I can focus firstly on the things that impact me and my team and set that as the first goal for each day. It makes sense to think of my things to do list in terms of earliest deadline first, but allowing misses on low priority things.
From a caching perspective, I'm also getting stronger at avoiding distraction, and having to context switch. I have my daily plan broken into blocks. If someone requires my help, I identify a low priority or low concentration block and ask them to wait until that time; the low priority work can usually be shifted forwards. It's an easy substitution to do mentally and usually I can continue with what I was doing before the interruption without losing too much momentum.
Embrace the Mess
When reading this book I had just built a new bookshelf and was in the process of transferring the books from three different rooms around the house into one consolidated library. The initial stacking was haphazard without too much thought to where the books went. The plan was to take an afternoon to get it all sorted to make searching easier.
Then I read the chapters on sorting and searching - it changed my approach. In fact it stopped it dead. If I consider how long it would take to sort the entire bookshelf, compared to the time to simply search and find a book in its current unordered state, the benefits do not stack up.
Given that I know each book intimately well - the colour of the spine and size of the book are known and familiar - it does not take long to dig out a book; a matter of minutes only. And realistically I refer to only a small number of the books on a regular basis; reference books and those that I like to dip into every now any then.
The chapter on caching gave me a new idea - I dedicated a space on a shelf at eye level for a cache. This is now the spot into which I can put frequently accessed books or those in my queue of new things to read. The rest of the books remain unordered and to date this has not bothered me nor have I spent long searching out books.
Conclusion
Planning a round the world trip, arranging the calender for sporting fixtures, placing fire engines in stations, sorting books in a library, determining the probability that your ticket will win the raffle, finding the best place to park, dealing with a friend who repeatedly cancels on you, or simply sorting your socks on laundry day; this book is bursting with practical applications for algorithms, both for personal and professional life.
A personal favourite of mine from the book is the possible explanation for why, as we get older, it perhaps takes a few moments longer to recall someone’s name or an old fact or figure, than when we were young; this may be just that we have accumulated much more information and have more data to search through. Unless we have used the data recently it will not be available in our memory cache. “Don’t say brain fart; say cache miss.”