LEARN Algorithms

Welcome

Fertile Questions for the Algorithms chapter of “How to Learn Computer Science”.

What does abstraction have to do with satellite navigation?

The real-world road network is too complicated to store in a computer. All we need are the major roads, where they meet, the distance between junctions. So a sat-nav stores a simplified version of the road network in its database, an abstraction of the real-world road network.

Of course, Dijkstra’s algorithm works on an abstraction of the road network, a simplified diagram that mathematicians call a graph. The graph consists of nodes, edges and edge weights, all stored as numbers in a data structure. Abstracting real world data into a suitable data structure, and then writing a matching algorithm to process it, are the key skills at the heart of programming. You want a program to detect cancer cells in biopsy samples? Get the image data into a suitable abstraction and then write a program to process the data, detecting the patterns of numbers that match indicators for cancer in the image. The first part of the process is data abstraction, which is not just “removing unnecessary detail”, it means retaining just the details required to answer questions about the data with a suitably matched algorithm.

“How to Learn Computer Science” page 102

How did Babbage use pattern-matching?

Babbage wanted a machine to solve polynomials, equations such as y = x² + 3x + 11. He knew that the values of x² followed a pattern, the results of the function f(x) = x² for each value from 1 to 7 are (1,4,9,16,25,36,49).

We now calculate the difference between each pair of consecutive terms, calling this the first-order difference (3,5,7,9,11,13). Now calculate the difference between each difference, which we call the second-order difference, we see the constant value 2.

Babbage had used pattern-matching to see that the difference of squares followed a regular sequence. In fact, a polynomial of any degree will eventually show a constant difference. For example, a function containing x^3 will have a constant third-order difference.

“How to Learn Computer Science” page 104

Why are there so many ways to express an algorithm?

Flowcharts, structured English, pseudocode and program code all have their benefits and drawbacks. Flowcharts are visual, and can help humans understand an algorithm. Structured English can help us get a bit more precise, but it can still be vague or ambiguous. Pseudocode tries to be precise without needing any programming language syntax, a pseudocode algorithm could be implemented in any programming language.

If we want to run an algorithm on a computer, then only program code will do. Each method of representing an algorithm is perfectly valid, and they all have their uses.

Why are searching and sorting algorithms so important?

Searching happens every day, on the web, in applications used by businesses and government departments, in schools. And searching a database or processing all of the content is quicker if the records are sorted in some kind of order.

Finding, adding or deleting data is much more efficient if the array or database table is in sorted order. Sorting is so important in computer science that there are at least a dozen basic algorithms in common use. Sorting is necessary to keep data organised, and the world creates 2.5 exabytes (2.5 x 10¹⁸ bytes) of data every day. As we saw earlier, finding useful information requires us to search the data, and sorted data is easier to search. Typical UK GCSE courses look at three sort algorithms: bubble, insertion and merge.

“How to Learn Computer Science” page 108

Why are there so many different algorithms for the same purpose?

Bubble sort is quick to code and runs in acceptably short time on small datasets, but gets very slow with large datasets. It’s time complexity makes it unsuitable for lots of data. Merge sort is fast on large datasets but harder to code and uses more memory.

Depending on the data, how much there is, how organised it is i.e. how close to sorted it already is, or if it is sorted in reverse order at the start, all these things affect the performance of different algorithms differently. You can see the differences on this YouTube video!