Ten years ago Jeanette Wing, proposed that computational thinking should be taught to children along with reading, writing and 'rithmetic. She wrote "Just as reading, writing, and arithmetic are fundamental skills every child learns, computational thinking is a skill needed for every citizen to function in today's global society. Computational thinking is an approach to solving problems, building systems, and understanding human behavior that draws on the power and limits of computing. Computational thinking is the use of abstraction to tackle complexity and the use of automation to tackle scale." Then, and since, I have been pretty sceptical of that position. This is partly because her examples of the ways in which computational thinking are useful to everyday life aren't very well developed in her initial paper. In fact, I used to teach a course entitled "Critical and Computational Thinking" but eventually I dropped the "Computational" bit from the title because I could never find any good meaty material for it. (In retrospect, this was not a surprise as I was in a computer science department at a time and in a sense we were fish in computational thinking water: it was just the way we thought).
In the past few years I have begun to change my mind and in the last weekend I became a convert. I read Algorithms to Live By by Brian Christian and Tom Griffiths and it is superb! It is an account of exactly how computational thinking can be applied to our everyday lives, written by a computer scientist and a cognitive scientist. It is satisfyingly geeky, but doesn't get bogged down in mathematical detail. The premise of the book is that computer scientists grapple with huge, messy, complex problems in the real world, and that the algorithms they have designed to solve those problems can give us insight into the problems that we stumble across routinely everyday. Seemingly mundane problems like knowing when to stop searching for the perfect hire in an applicant pool, or how to schedule tasks in an over crowded day are more complex than we give them credit for. In fact, computer scientists and mathematicians have devoted decades to solving theoretical problems which are structurally identical to those we encounter in our lives. In some cases, they have found optimal solutions which Christian and Griffiths make a good job of relating to the real world examples. In other cases, the problems are so thorny as to be intractable - because the solutions take so long to calculate - or indeed completely insoluble.
The authors make the point that computer science has moved away from reliance on algorithms which exhaustively and painstakingly grind through a series of steps until they find the right answer. Instead developing algorithms for"tackling real-world tasks requires being comfortable with chance, trading off time with accuracy and using approximations" (p5). This means that our best solutions for solving complex problems might not be guaranteed to be correct, or accurate and might give different answers each time. This is quite a different characterisation of algorithms to the watered down version of algorithms which has recently been used in schools where children give step by step instructions to aliens about how to make jam sandwiches. (I will save my jam sandwich rant for another day).
Similarly, the authors note, "people need to make decisions while dealing with uncertainty, time constraints, partial information and a rapidly changing world" (p6). Findings from how computer science has tackled problems of this sort suggest advice like "Don't always consider all your options. Don't necessarily go for the option that seems best every time. Make a mess on occasion. Travel light. Let things wait. Trust your instincts and don't think too long..." (p6). And the best bit about these nuggets of wisdom is that they are not fluffy fortune cookie drivel from a self-help book; they have formal mathematical proofs behind them.
To be a computer scientist is to make peace with the idea of trade-offs. Do you want the problem solved quickly with an approximate answer, or do you want the exact solution so much that you can wait for ages? How much resource can you throw at the problem to get it solved in a reasonable time? Once you accept that trade-offs are built into many problems, it is liberating because it takes the pressure off you personally. Here's an example:everyone has finite time available to do their jobs, even academics. Every new task which gets added to your academic workload means you have less time to allocate to existing tasks. The more papers you write, the less time you have to review papers for a journal. You cannot do it all. You have to make choices about which tasks to prioritise to optimise your own job satisfaction. And there is simply no point in feeling guilty about the tasks which you didn't have time to do.
Here are some of the topics in the book which I found particularly interesting.
Searching and Sorting
Computer scientists love to sort, and they spend a lot of time analysing the efficiency of different sorting methods. Some algorithms for sorting are better than others. Sorting goes hand in hand with searching because it is generally easier to locate an item in a sorted collection than ferreting around in a dirty great heap. "The basic principle is this: the effort expended on sorting materials is just a preemptive strike against the effort it'll take to search through them later." (p72). This is one reason why it makes sense to sort your clean laundry into different drawers - you sort laundry up front when you have time at the weekend so that when you are rushing around in the weekday mornings half-asleep you can lay your hand on your socks quickly. However, Christian and Griffiths advise to "err on the side of messiness... Sorting something you will never search is a complete waste; searching something you never sorted is merely inefficient" (p72). It's another trade-off. It will take you a long time to sort your books shelves into alphabetical order (if you have a large set of books) but you may not often need to search for a book. From this point of view, you'd be better to accept the trade-off that it might take you a while to uncover a book when you do need it than sink a day into sorting your books upfront. As a more commonly occurring example: this principle says it's a waste of time to sort your email into folders as it arrives. It is more common to get a message than it is to need to search for one, and furthermore your computer is able to perform a highly efficient search for you should the need arise (unless you happen to use Outlook, in my experience). So a tidy inbox is a sign of wasted time.
The sort/search trade-off is a long running debate in my house with respect to my son's giant Lego collection. It's easiest to store the Lego by dumping it into a big box (no sort), but when it comes to finding fiddly bits when you're making a model (search) it means endless scrabbling in the box. My husband attempts to sort the pieces into different box according to size and shape, but that's a) hard to maintain and b) time consuming to set up. In theory, setting it up is a high one time cost which should then pay off in the future. Unless, of course, someone drops the Lego boxes all over the stairs so an afternoon of sorting is lost. Oops.
Caching
So apparently there are lots of books devoted to telling people how to organise their possessions which dish out computational contradictory advice. If you are having a spring clean, you need to decide what to keep and then how to arrange those things. Are you going to take the advice of the clutter guru who tells you to group like things together? Or to consider when you bought it? When you last used it? Or indeed, quantify how much joy it is likely to bring you? It turns out that the techniques that computer scientists use to store information are useful here. There's a trade-off between size and speed in storage devices: you can't have limitless lightning fast storage so computer architecture generally compromises by using a hierarchical combination of small amounts of very fast memory and large amounts of slower storage devices (like hard discs). If you can predict which items of data are likely to be needed next, you can speed things up by storing those items in fast memory where you can get at them quickly. In fact, you can have a series of caches and shuffle data between them depending on when they're likely to be needed next. This is a bit like library books. If you're studying in the library, you take a few of the most relevant books to your table so you can refer to them easily. If you can't find what you need in this cache, you can go and look on the library shelf. In some cases you may have to ask the librarian to fetch the book from stacks storage in the basement, or indeed make a request for it to be brought from an off-site repository. The cache which stores the data which is likely to be used next should be physically closest to where the data will be used. In libraries, the books which will be in demand should be on easy to reach shelves and on computer chips, fast access memory should be situated close to the processor.
So what's the best way to predict what data will be needed in the immediate future? How do you decide which items get kicked out to free up precious space in the cache? It turns out that the Least Recently Used approach is optimal. The items which you used most recently are likely to be needed again soon, and the ones you haven't used for a bit probably won't needed again for a while.
Applying this to our spring cleaning, our authors have several pieces of advice based on caching. If space is a a premium, it makes sense to throw away items which you haven't used for a while rather than items you bought a while ago. You might have a very old t-shirt which you wear regularly for jogging which would be a better candidate to keep than a smart suit of the same vintage which you last wore in 2008. A legitimate objection to this is the cost of the item in the first place - why would you throw away an expensive suit? Well, if you have the space, you might want to move the least recently used items such as the suit to a secondary storage system farther away from your main wardrobe (like a box in the attic). Another lesson is to have storage for items close to their point of use (like wellies at the back door). The authors have no comment to make on how to predict expected joy from one's possessions, but I bet if pressed, they would apply some form of Bayes rule to the prior joy they have brought you.
One of my favourite results from this part of the book stems from the maths of self-organising lists. A pile of papers on your desk is not chaotic, it's optimal. Keep your papers in a pile, search the pile from top to bottom. When you pull out an item put it back on top rather than where you found it.That is the best way you can organise the documents to help you find an item quickly in the future. So there.
Scheduling
Processors and people alike need to schedule time to complete multiple tasks, taking into account possible unpredictable interruptions. This can actually be a really hard problem to solve (84% of scheduling problems are intractable according to the authors) so it's no wonder many people find it stressful. What algorithms can help us here? The answer depends on what you're trying to optimise - once again we encounter trade-offs. Suppose you care about reducing the maximum time a customer has to wait. Then your optimal strategy is to start with the soonest due task and work your way forwards to the task due last (the Earliest Due Date approach). If you're concerned about reducing the number of late projects then Moore's Algorithm is your friend. Proceed as for the Earliest Due Date but if it looks as though you are going to start missing deadlines, stop and consider the tasks remaining on your to-do list. Throw out the biggest item (that which would take longest to complete). Then at the very end, you can go back to the items which were eliminated from the to-do list and do them in any order because they're late by that time anyway.
If you're more concerned about how much you get done, then the Shortest Processing Time approach will work. Work out how long each task is likely to take, and then always do the quickest task you can. This lets you race through items on your list to-do quickly, but it does ignore that some tasks are more important than others. You can modify this approach by assigning an importance weight to each item on the list, then divide the importance by how long it'll take you to complete. Then do the tasks in order of importance-by-unit of time. This gives the rule of thumb: only prioritise a task that takes twice as long if its twice as important. You'd think that prioritising important weighty tasks would be a good bet but you also need to watch out for unfortunate side effects of dependencies between tasks. In short, a seemingly important small task should be given priority if an important task has to wait for it to be completed. (In operating systems design this is called priority inheritance).
What should you do if you get interrupted with a new task while you're working your way through your to-do list? Shortest Processing Time is still a good approach. As each task comes in, evaluate the importance-by-time-unit. If it's higher than the task you are working on, switch to the new task. Otherwise, stick with the current task. This reactive approach is easier to computer than elaborate re-planning and gives pretty good results.
Still, too much multi-tasking caused by interruptions does introduce additional problems. In operating systems, there is a concept of thrashing whereby the processor spends so much time swapping information in and out of memory for each new task that it never gets enough time to actually perform the task before it needs to switch again. In a state of thrashing, the processor is working to capacity but not completing any tasks. Does this sound familiar? You start to write an article, when the phone rings, and you're just writing down the new task the phone call brought up when someone knocks on your door with a new request. Trying to remember where you were with the writing task will take some time, and you can only hope that you can remember it and get some more words on the page before the next interruption. This is why it is a good idea to turn off your email if you're trying to get an important task done - context switching has an overhead.
Another trade-off: you can optimise for responsiveness or you can optimise for throughput. You can get back to student emails quickly or you can get a large number of exams marked, but if you favour one then the other will suffer. The theory would suggest that you should decide what your minimum acceptable level for responsiveness should be (e.g. how quickly do you need to reply to an email?). Once you have decided that, stay on a single task for as long as possible without overstepping the minimal responsiveness level. You shouldn't try to be more responsive than the minimum acceptable level. You could also time box so that you never spend less time on a task than it takes to remember what it is all about. For example, the pomodoro technique suggests focusing on a single task for 25 minutes without interruption. Lastly, applying interrupt coalescing might help. Instead of interrupting a task as a new request comes in, wait for a fixed interval before before checking for new tasks and then handle similar requests in a batch. For example, you could decide to only check your email once a day and deal with messages then and only then.
Reflection
I enjoyed reading Algorithms to Live By because it is an in depth justification of why and how computational thinking can be applied to everyday life. The examples in the book refer to the everyday life of adults, probably most for those of us in knowledge economy jobs. The authors weren't primarily setting out to explain computer science concepts for their own sake (although I think the books does this pretty well!). For these reasons, I don't the book can be used directly as a way to teach children about computational thinking. But I do believe that the algorithms and examples in the book can be a starting point for developing classroom activities along with teachers who understand what matters to children, and how best to explain concepts to different age groups. This is what I intend to do this summer.
Recent Comments