Computer Science › Section A · Introduction to computer science › Topic A.1
Algorithms and what computer science studies
Every app, game and search engine runs on a carefully written list of steps. Computer science is, at its heart, the study of those step-by-step methods: how to find them, write them down, run them and understand their limits.
More than the study of machines
It is easy to assume that computer science is about computers in the way that car mechanics is about cars. The machines matter, but the deeper subject is computation itself: which tasks can be carried out by following precise steps, how quickly, and how reliably. Computer scientists study the methods, the data they work on, the machines that run them, and the systems built from them. Data are raw values; they become information once organised and interpreted. That breadth is why the field reaches into mathematics, biology, linguistics and business.
What an algorithm is
Put simply, an algorithm is a list of instructions that spells out how to carry out a task. You already follow many: a recipe for a cake, directions across an unfamiliar town, the printed steps for running a washing machine. For a computer, though, the steps must be precise enough that no judgement is needed: each one must be unambiguous, each must be something the machine can actually do, and the whole process must come to an end. The topic "The concept of an algorithm" gives the formal definition later in the course.
Programs, software and hardware
An algorithm is an idea; a program is a representation of that idea in a form a machine can carry out. Programming, or coding, is the work of turning an algorithm into a program and getting it onto the machine. Programs and the algorithms they represent are together called software: system software, such as an operating system, and application software, such as a browser or game. The physical equipment that runs them, such as the processor, memory chips, storage devices, screen and keyboard, is called hardware. Firmware sits between them: software held in a device's non-volatile memory, such as the start-up code that runs the moment a computer is switched on.
Algorithms before computers
The search for algorithms began in mathematics, centuries before electronic machines. Mathematicians wanted one set of directions that would solve every problem of a given type. School long division is an example: it works for any two whole numbers, however many digits they have. Another, described in Euclid's Elements about 2,300 years ago, finds the largest whole number that divides both of two positive whole numbers. The word algorithm itself comes from al-Khwarizmi, a scholar who worked in Baghdad in the 9th century and whose book on Hindu-Arabic numerals, once translated into Latin, helped spread those methods of calculation in medieval Europe.
Worked example: Euclid's algorithm
Find the greatest common divisor (GCD) of 252 and 198. The method: let M be the larger number and N the smaller; work out the remainder R when M is divided by N; if R is 0, the answer is N; otherwise replace M with N and N with R, and repeat. 1. M = 252, N = 198: 252 = 1 × 198 + 54, so R = 54. 2. M = 198, N = 54: 198 = 3 × 54 + 36, so R = 36. 3. M = 54, N = 36: 54 = 1 × 36 + 18, so R = 18. 4. M = 36, N = 18: 36 = 2 × 18 + 0, so R = 0 and the GCD is 18. 5. Check: 252 = 18 × 14 and 198 = 18 × 11, and 14 and 11 share no factor, so 18 is the greatest.
The intelligence lives in the steps
Notice what happened in that example: you found the GCD without needing to know why Euclid's method works. Once an algorithm exists, carrying out the task is reduced to following directions. In a sense, the cleverness needed to solve the problem has been captured in the algorithm itself. This is exactly what makes computers useful. A machine that understands nothing can still perform a task brilliantly, provided someone has discovered an algorithm for it and expressed it as a program. It also sets a boundary: a machine can only do what some algorithm can describe.
The limits of algorithms
Are there problems that no algorithm can solve? In the 1930s mathematicians showed that the answer is yes. In 1931 Kurt Gödel proved his incompleteness theorem: any consistent formal system of rules rich enough to express ordinary arithmetic contains true statements that cannot be proved within that system. A few years later, in 1936, Alan Turing showed that some well-defined questions about programs cannot be answered by any algorithm at all. Studying what algorithms can and cannot do helped create computer science as a field, and the course's final section returns to these limits.
Worked example: making directions precise
A friend's note says: "Look through the stack of test papers and find the top score." Turn it into an algorithm a machine could follow for the scores 64, 81, 77, 92, 58. 1. Set BEST to the first score, 64. 2. For each remaining score, compare it with BEST; if it is larger, replace BEST with it. 3. Compare 81 with 64: larger, so BEST = 81. 4. Compare 77 with 81: not larger, so BEST stays 81. 5. Compare 92 with 81: larger, so BEST = 92. 6. Compare 58 with 92: not larger. 7. No scores remain, so stop and report BEST = 92. Every step is unambiguous, each is a simple comparison, and the process ends because the list is finite.
Computational thinking
The habits used to design algorithms are useful well beyond programming, and together they are often called computational thinking. Decomposition breaks a large problem into smaller parts. Pattern recognition spots similarities, so one solution can be reused. Abstraction keeps the details that matter and ignores the rest; the topic "The big themes of computer science and its impact on society" develops this idea. Algorithm design then writes the solution as clear steps. Planning a school timetable uses all four: split it into teachers, rooms and periods; notice that every science lab needs a lab room; ignore irrelevant details such as room colours; then assign classes step by step so that no teacher or room is booked twice.
Common mistakes to avoid
First, treating a program and an algorithm as the same thing: one algorithm can be written as many different programs, in different languages. Second, accepting vague steps such as "stir until it looks right" or "pick a good one": a machine cannot exercise judgement, so every step must be precise. Third, forgetting that an algorithm must stop; a set of steps that can loop forever does not define a complete task. Fourth, assuming any well-stated problem can be solved by a computer given enough speed: some problems have no algorithm at all.
Key takeaways
Computer science studies computation: algorithms, the data they process, the machines that run them and the systems built from them. An algorithm is a set of precise, executable steps that defines a terminating process; a program represents an algorithm for a machine. Software is programs; hardware is the equipment; firmware is software held in a device's non-volatile memory. Long division and Euclid's GCD method predate computers; the word comes from al-Khwarizmi. Following an algorithm needs no understanding of why it works. Gödel and Turing showed that some problems lie beyond any algorithm. Computational thinking combines decomposition, pattern recognition, abstraction and algorithm design.
Flashcards
Flashcard
The study of computation: algorithms, data, machines and the systems built from them
Test your understanding
Question 1 of 5
Using Euclid's algorithm, what is the greatest common divisor of 84 and 36?
Question 2 of 5
Which statement correctly describes the relationship between an algorithm and a program?
Question 3 of 5
Which instruction would stop a set of directions from being a usable algorithm for a machine?
Question 4 of 5
Planning a timetable, a student notices that every chemistry, biology and physics class needs a lab room, so one rule handles all three. Which part of computational thinking is this?
Question 5 of 5
What did the work of Gödel and Turing in the 1930s show about algorithms?