Pīkau 18: Comparing algorithms

Introduction

Links to existing knowledge

You might already know some of this.

If students are picking up certificates, is it a good idea to sort the certificates into alphabetical order first, or is it pretty much as fast just to look for each one in a randomly ordered pile?

Is it quicker to go through all the laundry taking out all the socks, then go through taking out all the shirts and so on, or is it better to go through putting each item into a pile as it is picked up? Is there a way to work out how efficient these two algorithms are without actually trying them out?

What if a postie had all the letters out of order for a street, and went up and down the street delivering them in the random order they were piled up, going to house number 45, then number 3, then 56, then 14, and so on? This would achieve the correct result, but how would you do it more efficiently?

There are probably many chores you do that you have found the optimal method (algorithm) for in your life, avoiding “busy” work that doesn’t improve the final result. Here we will look at how that translates into the programming world.

Exploring sorting algorithm performance

Here Tim and Joanne look at a sorting problem and two algorithms that can be used to solve it. Once again, they show the results in a graph that highlights the differences in efficiency between the two algorithms. The approach in this video builds on the method of using balance scales to explore sorting algorithms that was used in Pīkau 10 - Getting programs right: the end-user and fast algorithms.

This video showed how two algorithms, solving the exact same problem (sorting items), can give very different results. Using a graph to analyze the results emphasises this difference.

Although we’ve focussed on sorting and searching, there are thousands of other purposes that people have designed algorithms for.

These include:

• matching data for similarity (such as DNA tests)
• cryptography (to encode and decode data)
• compression (to reduce the space that data takes up)
• scheduling (such as working out which tasks on a large job need to be done first)
• playing games (such as chess)
• recognising objects in images (such as faces).

It gets worse

In this video Tim explores some real life problems that we are yet to find fast enough algorithms (solutions) for, even though a lot of effort has gone into doing so and the payoff would be large (there’s even a million dollar prize involved!).

As you saw, there is a surprising number of problems computer scientists have not been able to find suitable algorithms for, and there are many problems that are thought to be “intractable” (take way too long to solve), even with the ever increasing capabilities of technology. This is where a programmer needs to recognise when their program will take an impossibly long amount of time, and consider making do with ‘good enough’ solutions - they might not be the optimal answer, but at least we get a timely result.

You can try out the Travelling Salesperson Problem (TSP) online solver that was demonstrated in the video at CS Field Guide - City Trip.

This problem needs to be solved by anyone doing many drop-offs, such as courier deliveries or vending machine reloading (or in the original form, a salesperson visiting a number of cities).

• click on “Add city"
• choose about 7 cities
• and then click on “Start” to get it to try all possible routes around those cities.

For a small number of cities it should be quite quick, but notice how the time needed grows exponentially as you add more cities. For 25 cities, it will eventually find the best route, but you might not want to wait around for the result.

There are many problems that we only have found exponential time algorithms for - so far! Some of the key ones are referred to as “NP-complete” - the word “complete” means that a solution for any one of them could be adapted for any of the others, so they all stand or fall together.

There’s a list of hundreds of these problems here: List of NP-complete problems
 

How efficiently can you pack a bin?

Here’s another example of an intractable problem. Have a go at packing bins yourself with this ever changing interactive - you should minimise the number of bins needed. Beware though, it can be addictive!

This interactive can be found here: CS Field Guide - Bin packing

For small versions of the problem like the one above, it’s not hard to solve it on a computer, but as the number of items to pack grows, the best known algorithms take an exponentially increasing amount of time to solve the problem. If you’re working for a courier company with thousands of packages and hundreds of containers, it’s not going to be feasible to find the perfect way to pack the “bins” (in the case the bins might be containers, or even trucks or planes), so we have to settle for solutions that are 'good enough'.

For more information

There are a number of relevant CS Unplugged activities on searching and sorting.

The Computer Science Field Guide has a whole chapter on algorithms covering these ideas in more detail (aimed at NCEA level students).

If you’re interested in the limits of computing, the author David Harel has a book on this aimed at informed lay-people, called “Computers Ltd: What They Really Can't Do”.

Link to programme design

Technological practice

Anticipating which parts of a program will run slowly, and being aware of the best possible algorithms to use in common situations, is a fundamental skill that software developers need to have. As students work with larger amounts of data they will likely encounter situations where a bad decision about an algorithm makes the software impossibly slow to use. This can be a good learning experience as long as they are encouraged to explore what is causing the issue, and how better algorithms could be used to address it. To connect this practice to the NZC in your programme, refer to Outcome Development and Evaluation.

Technological knowledge

Many of the most popular apps and digital systems rely on searching. Although search engines are an obvious application, the “Edit” menu of a lot of software will have a “Find” command that relies on a searching algorithm, and every time a customer logs in or swipes a card on a digital system, a search is made to look up their details to allow access, and then to personalise their experience. Beyond everyday applications, whole companies have been founded on particular algorithms, such as finding optimal routes on a map, finding potential friends on a social network, recognising faces in scanned images, or detecting patterns in shopper activity to make buying recommendations. Students won’t have encountered all these algorithms, but they need to know that there are thousands of algorithms that have been invented, and be able to take advantage of these to “build on the shoulders of giants” rather than “reinvent the wheel”. To incorporate this knowledge refer to Technological Systems.

Nature of technology

It may come as a surprise to students that there are many things we don’t know about algorithms. There are hundreds of problems for which all known algorithms are intractable, yet no-one has proved that we won’t find good solutions to these problems. This is a conundrum that has puzzled researchers for decades, and it is one of several reasons that the exponential increase in computing speed doesn’t mean that one day we might expect to be able to make these algorithms fast enough to be useful. Exploring these limitations of what computers can do helps students to think about the future of computing in an informed way. Perhaps quantum computing will break through these problems, or perhaps someone will find a fast algorithm for conventional computers. There’s so much that we don’t know about what computers can do. Refer to Characteristics of Technological Outcomes for more information.

Algorithms have a direct impact on the environment. An important reason that fast algorithms are desirable is that they use less electrical energy because the computation finishes faster. For large companies that operate data warehouses with millions of computers, a small speed-up in an algorithm could save huge amounts of energy, which in turn reduces their impact on the environment. It would be an interesting exercise to estimate the impact on the environment (energy consumption) for one search on a search engine or to make a posting on a social network. One positive impact of algorithms is helping vehicles to follow shorter routes, saving fuel and reducing pollution. This then raises the interesting question of whether the energy used to calculate a shorter route is less than the energy saved by the vehicle that follows that shorter route. Investigating the ways that algorithms can both help and harm the environment can follow many avenues!

Estimating the speed of algorithms can provide rich material for statistics investigations. When talking about the “average” number of comparisons that sequential search makes, a more accurate estimate can be made by assuming that the key is equally likely to be at any place in the list, and working out the average over all these possibilities. A related option is to do a statistical experiment, measure how long it takes in a large number of cases, and plotting or averaging the times taken. The average case for an algorithm is a pragmatic measure of how useful it will be and provides great material for statistical analysis.

Facilitation notes

If you are working through this pīkau as a group feel free to download and use these facilitation notes:

• Facilitation notes - Comparing algorithms