Computer Science › Section F · Algorithms › Topic F.2

Representing algorithms with pseudocode

An algorithm only helps if it can be written down so that nobody misreads it. This topic shows how precise building blocks called primitives remove ambiguity, and sets out the pseudocode used for every algorithm in this section.

Why the way we write matters

The previous topic, "The concept of an algorithm", separated an algorithm from its representation. Writing algorithms in everyday English causes two kinds of trouble. Words can carry more than one meaning: "The chicken is ready to eat" might describe dinner or a hungry bird. And the level of detail may not suit the reader: "make a white sauce" is a complete instruction for a chef but useless to a beginner. Neither problem lies in the algorithm itself; both come from the language used to express it. Computer science tackles both by agreeing on a fixed set of precisely defined building blocks.

Primitives, syntax and semantics

A primitive is a basic building block of a representation with an agreed, exact meaning. Each primitive has a syntax, the symbols used to write it, and a semantics, what it means. The symbol + is syntax; its semantics is addition, so 2 + 3 gives 5. Context can change the semantics behind one syntax: in Python, "data" + "base" joins two strings to give "database". A collection of primitives, together with rules for combining them into larger instructions, makes up a programming language. Because every primitive is defined in advance, a representation built only from primitives has no hidden ambiguity and a uniform level of detail.

Levels of primitives

The instructions a CPU can execute, met in "Machine language", are primitives too, but writing whole algorithms with them is slow and error-prone. Instead, higher-level primitives are built out of lower-level ones, and each becomes a tool in its own right. A single while statement, for example, is carried out as several machine instructions. Writing a function, as described below, is the same idea on a small scale: you name a group of steps and then use it as if it were one primitive. The topic "Language implementation: translation and compilers" explains how high-level primitives are turned back into machine instructions.

What pseudocode is

Pseudocode is an informal notation for writing algorithms while you design them. It is more precise than English but easier to read than a real programming language, and it ignores fussy details such as punctuation rules. Pseudocode styles usually borrow from a well-known language; older textbooks echoed Algol and Pascal, and many newer ones, including this course, look like Python. The one firm requirement is consistency: each recurring structure must always be written the same way. In the 1950s and 1960s designers drew flowcharts, boxes joined by arrows, but large ones became tangles of crossing lines, so today flowcharts are used mainly to present structure, not to design it.

Our notation: names and choices

To name a computed value we write Name = expression, as in Total = Price + Tax. That line is an assignment: it stores the value of the right-hand side under the name on the left. To compare we write == for "equals", != for "is not equal to", and <, <=, > and >=. To choose between two activities we write if (condition): with the activity indented on the lines below, optionally followed by else: and a second indented activity. Indentation is part of the notation, as in Python: it shows exactly which lines belong to which structure. Names are single words, written in Pascal case such as TotalCost (camel case, totalCost, and snake case, total_cost, are other common styles).

Our notation: repetition, lists and functions

while (condition): repeats its indented body as long as the condition is true, checking it before every pass. repeat: runs its body, then checks until (condition) and goes round again if the condition is still false, so the body always runs at least once. for X in List: runs its body once for each entry of the list, with X standing for each entry in turn. L[i] is the entry at position i of list L, positions run from 1 to length(L), and [12, 7, 19] writes a list out in full. def Name(Parameters): starts a function, and return Value hands a result back. Sequencing, selection and iteration are enough to build any algorithm, a result proved by Böhm and Jacopini in 1966.

Functions and parameters

A function packages steps under a name so they can be reused. Its parameters are general names for the data it works on, listed in brackets after the name, so def Sort(List): can sort any list, not one particular list. When the function is used, or called, you supply arguments, the actual values: Sort(GuestList) or Sort(Prices). Inside the function, every mention of List refers to whichever argument was passed in. Functions can call other functions, so small algorithms combine into larger ones. The topic "Procedural units: functions and parameters" shows how real languages pass arguments.

Worked example: from English to pseudocode

A shop's rule: "Orders over $50 get 10% off. Delivery costs $5, but it is free on orders over $100."

\begin{array}{l} \texttt{def Total(Price):} \\ \quad \texttt{if (Price > 50):} \\ \qquad \texttt{Cost = Price * 0.9} \\ \quad \texttt{else:} \\ \qquad \texttt{Cost = Price} \\ \quad \texttt{if (Price <= 100):} \\ \qquad \texttt{Cost = Cost + 5} \\ \quad \texttt{return Cost} \end{array}

1. Total(40): no discount, delivery added, $45. 2. Total(80): $72 after discount, plus $5, $77. 3. Total(120): $108, free delivery. 4. Writing the code exposed an ambiguity: is "over $100" judged before or after the discount? This version tests the original price, so Total(110) is $99. Testing Cost instead would give $99 + $5 = $104.

Worked example: a function with a loop

Count how many entries of a list exceed a limit.

\begin{array}{l} \texttt{def CountAbove(List, Limit):} \\ \quad \texttt{Count = 0} \\ \quad \texttt{for X in List:} \\ \qquad \texttt{if (X > Limit):} \\ \qquad\quad \texttt{Count = Count + 1} \\ \quad \texttt{return Count} \end{array}

Call CountAbove([12, 7, 19, 3, 15], 10). 1. Count starts at 0. 2. X = 12 exceeds 10, so Count becomes 1. 3. X = 7 does not. 4. X = 19 does, so Count is 2. 5. X = 3 does not. 6. X = 15 does, so Count is 3. 7. The loop ends and the function returns 3. The same function, unchanged, answers CountAbove(Scores, 50) for any list of scores.

Common mistakes to avoid

First, mixing = and ==: = stores a value, == asks whether two values are equal. Second, careless indentation: in if (Raining): if (Windy): take a raincoat, else: take an umbrella, the else lines up under the inner if, so on a dry day nothing is taken; move the else out one level and it would apply to dry days instead. Third, writing a fixed list into a function instead of using a parameter. Fourth, inconsistent notation, such as switching between while and "keep going until" for the same structure. Fifth, leaving a step too vague for the intended reader.

Key takeaways

Natural language is ambiguous and its level of detail varies, so algorithms are built from primitives with exact syntax (form) and semantics (meaning). Primitives plus combining rules make a programming language, and higher-level primitives are built from lower-level ones. Pseudocode is a consistent, informal design notation. Ours uses Name = expression, ==, if and else, while, repeat and until, for X in List, L[i] with positions from 1, and def with parameters and return. Indentation carries meaning, and sequencing, selection and iteration can express any algorithm.

Flashcards

Flashcard

Primitive

A basic building block of a representation with an exact, agreed meaning

Removes ambiguity and fixes the level of detail.

Test your understanding

Question 1 of 5

Using the Total(Price) function from the worked example, which tests Price > 50 for the discount and Price <= 100 for delivery, what does Total(110) return?

Question 2 of 5

In Python, 2 + 3 gives 5, but "data" + "base" gives "database". What does this show?

Question 3 of 5

What does CountAbove([4, 11, 10, 25], 10) return, using the function from the worked example?

Question 4 of 5

Why is a sorting function written as def Sort(List): instead of naming one particular list inside it?

Question 5 of 5

In the code if (Raining): if (Windy): take a raincoat, else: take an umbrella, the else is indented to line up with the inner if. What is taken on a dry, windy day?

← Previous topicNext topic →