Pseudo-code¶
Part 1 · Basic algorithms · Chapter 2 · Lecture notes, volume 1 (PDF) · Exercises: Pseudo-code
Introduction¶
In the previous chapter we have seen how the data of an algorithm, the numbers, are represented. In this chapter we fix the language used in these notes to describe the algorithms themselves: the pseudo-code. Pseudo-code is precise enough to describe every step of an algorithm without ambiguity, and simple enough to be read without knowing any programming language.
The chapter introduces the elements of pseudo-code one at a time, from the simplest to the most structured:
-
variables, declarations and assignments, and the basic operations on them;
-
the basic constructs that control the order of execution: conditional statements, loops, and the loop control statements break and continue;
-
arrays with one, two and more indices;
-
functions, which give a name to an algorithm, with its input and its output;
-
sets.
Each construct is followed by examples, executed step by step on small instances. Executing an algorithm by hand, while keeping track of the values of its variables, is the best way to understand what it does.
2.1 Introduction to pseudo-code¶
Definition 2.1: algorithm
An algorithm is a finite sequence of unambiguous instructions that, starting from some data given as input, produces a result given as output in a finite number of steps.
Definition 2.2: pseudo-code
Pseudo-code is a high-level description of an algorithm that uses a mixture of natural language and programming language-like structures.
-
Pseudo-code is not meant to be executed by a computer, but rather to communicate the logic of an algorithm to humans.
-
Pseudo-code allows us to focus on the logic and structure of an algorithm without worrying about the syntax of a specific programming language.
-
Convention: in these notes, all reserved words (keywords) of pseudo-code are written in bold, e.g., if, while, for, return, etc.
Advantages of pseudo-code:
-
Language-independent: it can be understood by programmers of different languages
-
Easy to write and modify
-
Focuses on the logic of the algorithm rather than on implementation details
-
Facilitates communication between developers and non-technical stakeholders
-
Useful for planning before actual coding
Key principles:
-
Use clear and descriptive variable names
-
Keep statements simple and concise
-
Use indentation to show structure and nesting
-
Use standard constructs (if-then-else, while, for, etc.)
-
Include comments when necessary to clarify complex operations
Recommended practices:
-
Indentation: use consistent indentation to show the block structure
-
Variables: use descriptive names in italics or regular text
-
Comments: add comments (in natural language) to explain complex steps
-
Input/Output: clearly specify the input parameters and the output (return values)
-
Line numbers: useful for referencing specific lines
-
Consistency: maintain the same notation and style throughout
2.2 Variables and assignments¶
The data of an algorithm are stored in variables: named containers whose value can change during the execution. A variable is first created with a declaration and then modified with assignments.
2.2.1 Variables¶
-
Variables must be declared before use
-
The declaration operator is “\(:=\)”
-
The declaration specifies the variable name and its initial value
Example 2.1: variable declaration
Seven variables declared with their initial values: integer, rational, \(-\infty\) and logical (true/false) values are all allowed.
2.2.2 Assignment¶
-
The assignment operator is “\(\leftarrow\)”
-
It assigns the value of an expression to a previously declared variable: first the expression on the right is evaluated, then its value replaces the old value of the variable
Example 2.2: assignment
With the variables of Example 2.1:
After the three assignments \(n = 10\), \(sum = 10 + 10 = 20\) and \(count = 1 + 1 = 2\). In the last assignment the same variable appears on both sides: the old value \(1\) is used to compute the new value \(2\).
Example 2.3: exchanging the values of two variables
To exchange the values of two variables \(x\) and \(y\) we need a third, temporary variable \(tmp\): the assignment \(x \leftarrow y\) alone would overwrite the old value of \(x\).
Step-by-step execution with \(x = 3\) and \(y = 8\):
| statement | \(x\) | \(y\) | \(tmp\) |
|---|---|---|---|
| – | \(3\) | \(8\) | – |
| \(tmp := x\) | \(3\) | \(8\) | \(3\) |
| \(x \leftarrow y\) | \(8\) | \(8\) | \(3\) |
| \(y \leftarrow tmp\) | \(8\) | \(3\) | \(3\) |
2.3 Basic operations¶
Expressions combine variables and values with the following operations.
Mathematical operations:
-
\(+, -, \times, /\): basic arithmetic
-
\(a \bmod b\): modulo, i.e., the remainder of the integer division of \(a\) by \(b\)
-
\(\lfloor x \rfloor\): floor (greatest integer \(\le x\))
-
\(\lceil x \rceil\): ceiling (smallest integer \(\ge x\))
-
\(|x|\): absolute value
-
\(\max(a, b)\), \(\min(a, b)\): maximum and minimum
Comparison operators:
-
\(=, \neq\): equal, not equal
-
\(<, \le, >, \ge\): less than, less than or equal to, greater than, greater than or equal to
Logical operators:
- and, or, not: logical operations
Input/Output:
-
read(variable): read input from the user
-
print(expression): output a value
Example 2.4: evaluating expressions
-
\(17 \bmod 5 = 2\), since \(17 = 3 \cdot 5 + 2\); in particular, an integer \(i\) is a multiple of \(3\) if and only if \(i \bmod 3 = 0\).
-
\(\lfloor 7/2 \rfloor = \lfloor 3.5 \rfloor = 3\) and \(\lceil 7/2 \rceil = \lceil 3.5 \rceil = 4\).
-
\(|-3| = 3\), \(\max(-3, 2) = 2\) and \(\min(-3, 2) = -3\).
-
\((5 > 3)\) and \((2 > 4)\) is false, while \((5 > 3)\) or \((2 > 4)\) is true.
2.4 Basic constructs¶
The statements of pseudo-code are executed one after the other, from top to bottom. Two kinds of constructs change this order: conditional statements, which execute a block only when a condition holds, and loops, which execute a block several times.
2.4.1 Conditional statements¶
If-then¶
- Executes a block of statements only if a condition is true
Example 2.5: if-then
Checking whether a number \(x\) is positive:
Step-by-step execution:
Instance 1: \(x = 5\)
| \(x\) | \(x > 0\)? | \(positive\) |
|---|---|---|
| – | – | false |
| \(5\) | Yes | true |
Output: 5 is positive
Instance 2: \(x = -3\)
| \(x\) | \(x > 0\)? | \(positive\) |
|---|---|---|
| – | – | false |
| \(-3\) | No | false |
Output: nothing is printed.
If-then-else¶
- Executes one block if the condition is true, and another block if it is false
Example 2.6: if-then-else
Computing the absolute value of a number \(x\):
Step-by-step execution:
Instance 1: \(x = 7\)
| \(x\) | \(x \ge 0\)? | \(result\) |
|---|---|---|
| – | – | \(0\) |
| \(7\) | Yes | \(7\) |
Result: \(result = 7\)
Instance 2: \(x = -4\)
| \(x\) | \(x \ge 0\)? | \(result\) |
|---|---|---|
| – | – | \(0\) |
| \(-4\) | No | \(4\) |
Result: \(result = 4\)
2.4.2 Loops¶
While loop¶
-
Repeats a block of statements while a condition is true
-
The condition is checked before each iteration
-
If the condition is initially false, the loop body is never executed
Example 2.7: while loop
Computing the sum of the numbers from \(1\) to \(n\):
Step-by-step execution:
Instance: \(n = 5\). Each row shows the value of \(i\) when the condition is checked, the outcome of the check, and the values of \(sum\) and \(i\) at the end of the iteration.
| \(i\) | \(i \le n\)? | \(sum\) | \(i\) (after) |
|---|---|---|---|
| – | – | \(0\) | \(1\) |
| \(1\) | Yes | \(1\) | \(2\) |
| \(2\) | Yes | \(3\) | \(3\) |
| \(3\) | Yes | \(6\) | \(4\) |
| \(4\) | Yes | \(10\) | \(5\) |
| \(5\) | Yes | \(15\) | \(6\) |
| \(6\) | No | \(15\) | – |
Result: \(sum = 15\)
In the previous example the number of iterations is known in advance. The while loop is necessary when it is not, as in the next example.
Example 2.8: while loop
Computing how many times a number \(x\) must be halved before it becomes smaller than or equal to a threshold \(\varepsilon > 0\):
Step-by-step execution:
Instance 1: \(x = 10\), \(\varepsilon = 1\)
| \(x\) | \(count\) | \(x > \varepsilon\)? | \(x\) (after) | \(count\) (after) |
|---|---|---|---|---|
| \(10\) | \(0\) | Yes | \(5\) | \(1\) |
| \(5\) | \(1\) | Yes | \(2.5\) | \(2\) |
| \(2.5\) | \(2\) | Yes | \(1.25\) | \(3\) |
| \(1.25\) | \(3\) | Yes | \(0.625\) | \(4\) |
| \(0.625\) | \(4\) | No \(\Rightarrow\) exit | – | \(4\) |
Result: \(count = 4\)
Instance 2: \(x = 100\), \(\varepsilon = 10\)
| \(x\) | \(count\) | \(x > \varepsilon\)? | \(x\) (after) | \(count\) (after) |
|---|---|---|---|---|
| \(100\) | \(0\) | Yes | \(50\) | \(1\) |
| \(50\) | \(1\) | Yes | \(25\) | \(2\) |
| \(25\) | \(2\) | Yes | \(12.5\) | \(3\) |
| \(12.5\) | \(3\) | Yes | \(6.25\) | \(4\) |
| \(6.25\) | \(4\) | No \(\Rightarrow\) exit | – | \(4\) |
Result: \(count = 4\)
For loop¶
-
Repeats a block of statements for a specified number of times
-
Typically used when the number of iterations is known in advance
The for loop is a compact way of writing a particular while loop: the loop variable is declared with the start value, the condition compares it with the end value, and it is increased by \(1\) at the end of each iteration.
The loop on the left is equivalent to the loop on the right:
In particular, the body is executed \(e - s + 1\) times if \(s \le e\), and it is never executed if \(s > e\).
Example 2.9: for loop
Computing the sum of the numbers from \(1\) to \(n\) with a for loop (compare with Example 2.7):
Step-by-step execution:
Instance: \(n = 5\)
| \(i\) | \(i \le n\)? | \(sum\) |
|---|---|---|
| – | – | \(0\) |
| \(1\) | Yes | \(1\) |
| \(2\) | Yes | \(3\) |
| \(3\) | Yes | \(6\) |
| \(4\) | Yes | \(10\) |
| \(5\) | Yes | \(15\) |
| \(6\) | No | \(15\) |
Result: \(sum = 15\)
The for loop can optionally use a step value, to increase the loop variable by values other than \(1\).
Example 2.10: for loop with step
Computing the sum of the first \(n\) even numbers (\(2, 4, \ldots, 2n\)):
Step-by-step execution:
Instance: \(n = 4\) (even numbers: \(2, 4, 6, 8\))
| \(i\) | \(i \le 2n\)? | \(sum\) |
|---|---|---|
| – | – | \(0\) |
| \(2\) | Yes | \(2\) |
| \(4\) | Yes | \(6\) |
| \(6\) | Yes | \(12\) |
| \(8\) | Yes | \(20\) |
| \(10\) | No | \(20\) |
Result: \(sum = 20\)
2.4.3 Loop control statements¶
Sometimes a loop must be interrupted before its natural end, or a single iteration must be skipped. Two statements serve these purposes.
Break statement¶
-
The break statement immediately exits the current loop
-
Execution continues with the first statement after the loop
-
Useful when a termination condition is met before the natural completion of the loop
Example 2.11: break statement
Computing the sum of the numbers from \(1\) to \(n\), stopping as soon as the sum exceeds a threshold \(t\).
With a while loop:
With a for loop:
Step-by-step execution (both loops):
Instance: \(n = 6\), \(t = 10\)
| \(i\) | \(sum\) | \(sum > t\)? |
|---|---|---|
| – | \(0\) | – |
| \(1\) | \(1\) | No |
| \(2\) | \(3\) | No |
| \(3\) | \(6\) | No |
| \(4\) | \(10\) | No |
| \(5\) | \(15\) | Yes \(\Rightarrow\) break |
Result: \(sum = 15\); the iteration with \(i = 6\) is never executed.
Continue statement¶
-
The continue statement skips the rest of the current iteration
-
Execution proceeds immediately with the next iteration of the loop (in a while loop, with the check of the condition)
-
Useful when certain iterations should be skipped based on a condition
Example 2.12: continue statement
Computing the sum of the numbers from \(1\) to \(n\), skipping the multiples of \(3\).
With a while loop:
With a for loop:
In the while loop the variable \(i\) must be increased before continue: otherwise the condition \(i \bmod 3 = 0\) would remain true forever and the loop would never end. In the for loop the increase is automatic.
Step-by-step execution (both loops):
Instance: \(n = 7\)
| \(i\) | \(i \bmod 3 = 0\)? | \(sum\) |
|---|---|---|
| – | – | \(0\) |
| \(1\) | No | \(1\) |
| \(2\) | No | \(3\) |
| \(3\) | Yes | \(3\) |
| \(4\) | No | \(7\) |
| \(5\) | No | \(12\) |
| \(6\) | Yes | \(12\) |
| \(7\) | No | \(19\) |
Result: \(sum = 19 = 1 + 2 + 4 + 5 + 7\)
Key points on the basic constructs.
-
if-then and if-then-else choose which block to execute according to a condition.
-
while repeats a block as long as a condition is true, checking it before each iteration; for repeats a block for each value of a loop variable from a start value to an end value.
-
break exits the loop; continue skips to the next iteration.
-
Executing a construct step by step on a small instance, with a table of the values of the variables, shows exactly what it does.
2.5 Arrays¶
Many algorithms work on a collection of values of the same kind, for instance a list of \(n\) numbers. Instead of declaring \(n\) different variables, we use an array.
-
Arrays are indexed collections of variables and must be declared before use
-
The declaration operator is “new array” followed by the index range
Example 2.13: array declaration
Creating an array of size \(n\), indexed from \(1\) to \(n\):
-
The notation \(a[i]\) denotes the variable at index \(i\)
-
Arrays are typically indexed starting from \(0\) or \(1\): in the pseudo-code of these notes the indices start from \(1\), so an array of \(n\) elements is \(a[1..n]\); in many programming languages, such as C++, the indices start from \(0\)
-
Each variable in the array must be initialized before access and use
-
To initialize all the elements to the same value, use a for loop:
Example 2.14: array assignment
Initializing and accessing the variables of an array \(a[1..n]\) (with \(n \ge 5\)):
With \(n = 5\) the array is \([0, 0, 0, 0, 0]\) after the loop, \(x = 0\), and the array is \([0, 0, 42, 0, 0]\) at the end.
2.5.1 Two-dimensional arrays¶
-
Two-dimensional arrays are indexed collections of variables with two indices and must be declared before use
-
The declaration operator is “new array” followed by the two index ranges
-
Two-dimensional arrays are typically indexed starting from \(0\) or \(1\) (from \(1\) in these notes)
Example 2.15: two-dimensional array declaration
Creating a two-dimensional array of size \(m \times n\) (indexed from \(1\) to \(m\) and from \(1\) to \(n\)):
-
The notation \(b[i][j]\) denotes the variable at row \(i\) and column \(j\)
-
Each variable in the array must be initialized before access and use
-
To initialize all the elements to the same value, use nested for loops:
Example 2.16: two-dimensional array assignment
Initializing and accessing the variables of a two-dimensional array \(b[1..m][1..n]\) (with \(m \ge 2\) and \(n \ge 3\)):
The outer loop runs over the rows and, for each row \(i\), the inner loop runs over all the columns: the elements are visited in the order \(b[1][1], b[1][2], \dots, b[1][n], b[2][1], \dots, b[m][n]\), for a total of \(m \cdot n\) assignments.
2.5.2 Multi-dimensional arrays¶
-
Multi-dimensional arrays are indexed collections of variables with multiple indices and must be declared before use
-
The declaration operator is “new array” followed by the index ranges for each dimension
Example 2.17: multi-dimensional array declaration
Creating a \(3\)-dimensional array of size \(p \times q \times r\) (indexed from \(1\) to \(p\), from \(1\) to \(q\), and from \(1\) to \(r\)):
-
The notation \(t[i_1][i_2]\cdots[i_k]\) denotes the variable at indices \(i_1, i_2, \ldots, i_k\)
-
Multi-dimensional arrays are typically indexed starting from \(0\) or \(1\) (from \(1\) in these notes)
-
Each variable in the array must be initialized before access and use
-
To initialize all the elements to the same value, use nested for loops (one per dimension):
Example 2.18: multi-dimensional array assignment
Initializing and accessing a \(3\)-dimensional array \(t[1..p][1..q][1..r]\) (with \(p \ge 2\), \(q \ge 2\) and \(r \ge 3\)):
2.6 Functions¶
The examples seen so far are fragments of pseudo-code that work on variables assumed to exist. A function turns such a fragment into a complete algorithm, with a name, an input and an output.
-
A function is a named, reusable block of code that performs a specific task
-
A function takes input data through its parameters and produces output data
-
The return statement terminates the function and specifies its results
-
Functions are typically used to implement algorithms or to perform specific computations that can be reused in different parts of a program
Syntax:
In the rest of these notes every algorithm is written as a function, inside a red box. The input states the preconditions on the data (for instance, that an array has at least one element): the function is guaranteed to work only when they hold.
Example 2.19: maximum value in an array
A function returning the maximum value in an array: the variable \(max\) starts from the first element and is updated whenever a larger element is found.
Algorithm: FindMaximum
Step-by-step execution:
Instance 1: \(a = [9, 12, 3, 16, 19, 11, 12]\), \(n=7\)
| \(i\) | \(a[i]\) | \(a[i] > max\)? | \(max\) |
|---|---|---|---|
| – | – | – | \(9\) |
| \(2\) | \(12\) | Yes | \(12\) |
| \(3\) | \(3\) | No | \(12\) |
| \(4\) | \(16\) | Yes | \(16\) |
| \(5\) | \(19\) | Yes | \(19\) |
| \(6\) | \(11\) | No | \(19\) |
| \(7\) | \(12\) | No | \(19\) |
Return: \(max = 19\)
Instance 2: \(a = [3, 7, 2, 9, 1]\), \(n=5\)
| \(i\) | \(a[i]\) | \(a[i] > max\)? | \(max\) |
|---|---|---|---|
| – | – | – | \(3\) |
| \(2\) | \(7\) | Yes | \(7\) |
| \(3\) | \(2\) | No | \(7\) |
| \(4\) | \(9\) | Yes | \(9\) |
| \(5\) | \(1\) | No | \(9\) |
Return: \(max = 9\)
Example 2.20: counting the positive elements of an array
A function counting the number of positive elements in an array:
Algorithm: CountPositive
Step-by-step execution:
Instance 1: \(a = [-2, 5, -1, 3, 0]\), \(n = 5\)
| \(i\) | \(a[i]\) | \(a[i] > 0\)? | \(count\) |
|---|---|---|---|
| – | – | – | \(0\) |
| \(1\) | \(-2\) | No | \(0\) |
| \(2\) | \(5\) | Yes | \(1\) |
| \(3\) | \(-1\) | No | \(1\) |
| \(4\) | \(3\) | Yes | \(2\) |
| \(5\) | \(0\) | No | \(2\) |
Return: \(count = 2\)
Instance 2: \(a = [4, -3, 7, 2]\), \(n = 4\)
| \(i\) | \(a[i]\) | \(a[i] > 0\)? | \(count\) |
|---|---|---|---|
| – | – | – | \(0\) |
| \(1\) | \(4\) | Yes | \(1\) |
| \(2\) | \(-3\) | No | \(1\) |
| \(3\) | \(7\) | Yes | \(2\) |
| \(4\) | \(2\) | Yes | \(3\) |
Return: \(count = 3\)
Example 2.21: checking whether an array is sorted
A function checking whether an array is sorted in non-decreasing order. The return statement inside the loop terminates the function as soon as two consecutive elements in the wrong order are found.
Algorithm: IsSorted
Step-by-step execution:
Instance 1: \(a = [2, 5, 7, 9]\), \(n = 4\)
| \(i\) | \(a[i]\) | \(a[i{+}1]\) | \(a[i] > a[i{+}1]\)? |
|---|---|---|---|
| \(1\) | \(2\) | \(5\) | No |
| \(2\) | \(5\) | \(7\) | No |
| \(3\) | \(7\) | \(9\) | No |
Return: true
Instance 2: \(a = [3, 1, 4, 2]\), \(n = 4\)
| \(i\) | \(a[i]\) | \(a[i{+}1]\) | \(a[i] > a[i{+}1]\)? |
|---|---|---|---|
| \(1\) | \(3\) | \(1\) | Yes |
Return: false, after a single comparison.
Example 2.22: scalar product of two arrays
A function computing the scalar product \(\sum_{i=1}^{n} a[i] \cdot b[i]\) of two arrays:
Algorithm: ScalarProduct
Step-by-step execution:
Instance 1: \(a = [1, 2, 3]\), \(b = [4, 5, 6]\), \(n = 3\)
| \(i\) | \(a[i]\) | \(b[i]\) | \(a[i]\cdot b[i]\) | \(prod\) |
|---|---|---|---|---|
| – | – | – | – | \(1 \cdot 4 = 4\) |
| \(2\) | \(2\) | \(5\) | \(10\) | \(4 + 10 = 14\) |
| \(3\) | \(3\) | \(6\) | \(18\) | \(14 + 18 = 32\) |
Return: \(prod = 32\)
Instance 2: \(a = [2, 0, -1]\), \(b = [3, 4, 5]\), \(n = 3\)
| \(i\) | \(a[i]\) | \(b[i]\) | \(a[i]\cdot b[i]\) | \(prod\) |
|---|---|---|---|---|
| – | – | – | – | \(2 \cdot 3 = 6\) |
| \(2\) | \(0\) | \(4\) | \(0\) | \(6 + 0 = 6\) |
| \(3\) | \(-1\) | \(5\) | \(-5\) | \(6 + (-5) = 1\) |
Return: \(prod = 1\)
Example 2.23: reversing an array
A function reversing the elements of an array: the element \(a[i]\) is exchanged with its symmetric element \(a[n-i+1]\), with the temporary variable of Example 2.3. Only \(\lfloor n/2 \rfloor\) exchanges are needed: with \(n\) odd, the middle element stays in place.
Algorithm: ReverseArray
Step-by-step execution:
Instance 1: \(a = [1, 2, 3, 4, 5]\), \(n = 5\), \(\lfloor 5/2 \rfloor = 2\) iterations
| \(i\) | exchange | array \(a\) (after the exchange) |
|---|---|---|
| – | – | \([1, 2, 3, 4, 5]\) |
| \(1\) | \(a[1] \leftrightarrow a[5]\) | \([5, 2, 3, 4, 1]\) |
| \(2\) | \(a[2] \leftrightarrow a[4]\) | \([5, 4, 3, 2, 1]\) |
Return: \(a = [5, 4, 3, 2, 1]\)
Instance 2: \(a = [10, 20, 30, 40]\), \(n = 4\), \(\lfloor 4/2 \rfloor = 2\) iterations
| \(i\) | exchange | array \(a\) (after the exchange) |
|---|---|---|
| – | – | \([10, 20, 30, 40]\) |
| \(1\) | \(a[1] \leftrightarrow a[4]\) | \([40, 20, 30, 10]\) |
| \(2\) | \(a[2] \leftrightarrow a[3]\) | \([40, 30, 20, 10]\) |
Return: \(a = [40, 30, 20, 10]\)
2.7 Sets¶
Arrays store values in positions. When only the membership of the values matters, and not their position or their repetitions, we use a set.
-
A set is an unordered collection of distinct elements
-
Sets must be declared before use with the new set operator; no size needs to be specified; when created, a set is empty
The main operators on sets are:
-
add: insert an element into the set (ignored if already present)
\[ \textbf{add} \ x \ \textbf{to} \ \text{set\_name} \] -
remove: delete an element from the set (ignored if not present)
\[ \textbf{remove} \ x \ \textbf{from} \ \text{set\_name} \] -
in: membership test, which evaluates to true if \(x\) belongs to the set
\[ x \ \textbf{in} \ \text{set\_name} \] -
size: cardinality (number of elements currently in the set)
\[ \textbf{size}(\text{set\_name}) \] -
foreach: loop over the elements of the set; by convention, in these notes the elements are visited in insertion order
- It is possible to loop over the elements of a set in a specific order by specifying a sorting criterion:
Example 2.24: set declaration and usage
Step-by-step execution:
Instance: \(n = 8\)
-
Step 1: the for loop adds \(2, 4, 6, 8\), so \(s = \{2, 4, 6, 8\}\).
-
Step 2: \(4\) belongs to \(s\): the output is
4 is in s. -
Step 3: after the removal, \(s = \{2, 6, 8\}\).
-
Step 4: the first foreach prints \(2, 6, 8\) (insertion order), then the cardinality \(3\) is printed.
-
Step 5: the last two loops print \(8, 6, 2\) and \(2, 6, 8\).
2.8 Style conventions¶
We conclude with a summary of the notation used in these notes, compared with other common choices.
Different authors may use slightly different conventions:
-
Declaration: \(:=\) (used in these notes) or \(=\) (some authors use the same symbol for both declaration and assignment)
-
Assignment: \(\leftarrow\) (used in these notes) or \(=\)
-
Array indexing: \(a[i]\) (used in these notes) or \(a_i\)
-
Two-dimensional array indexing: \(b[i][j]\) (used in these notes) or \(b_{ij}\)
-
Comments: // comment, # comment, or (* comment *)
The important thing is to be consistent and clear!
Key points of the chapter.
-
Variables are declared with \(:=\) and modified with \(\leftarrow\).
-
Conditional statements and loops (if, while, for, with break and continue) control the order of execution.
-
Arrays \(a[1..n]\), \(b[1..m][1..n]\), … are indexed from \(1\) in pseudo-code; sets store distinct elements without positions.
-
An algorithm is written as a function with its input (including the preconditions), its output and a return statement.
Exercises on this chapter: Pseudo-code