5.1 Algorithms and Pseudocode

Chapter 4 studied structures: functions map inputs to outputs, relations record connections, and partial orders express dependencies. We now ask a new question:

> What finite procedure transforms a permitted input into the required output?

That procedure is an algorithm. Algorithms appear in software, but the idea is broader than a programming language. Long division, following a recipe, finding the largest card in a hand, and arranging tasks by prerequisites are all procedures.

What makes a procedure an algorithm?

An algorithm is a finite, precisely described sequence of steps for solving a specified problem.

Four parts must be clear:

1. Input: the data the procedure receives.

2. Output: the result it promises to produce.

3. Allowed steps: operations whose meaning is unambiguous.

4. Termination: the procedure finishes after finitely many steps for every permitted input.

Consider the problem “find the larger of two real numbers.”

• Input: real numbers $a$ and $b$.

• Output: $\max(a,b)$, the larger value; if they are equal, that common value.

• Allowed steps: compare the numbers and return one of them.

A precise algorithm is:

LARGER(a, b)
    if a ≥ b
        return a
    else
        return b

The indentation shows which return belongs to each branch.

Compare this with “look at the numbers and choose the better one.” The phrase “better” is undefined, so two readers could perform different operations. An algorithm must be precise enough that the same input follows the same specified rules.

Algorithms are not programs

An algorithm is the language-independent method. A program is an implementation of that method in a language such as Python, JavaScript, or Java.

The same algorithm can have many programs. Pseudocode lets us discuss the essential reasoning without requiring the syntax of one programming language.

Reading pseudocode notation

This course uses a small set of conventions.

Assignment

An assignment changes the value stored in a variable:

total ← 0
total ← total + 5

After the first line, $total=0$. The second line reads the old value, adds $5$, and stores the new value, so $total=5$.

The arrow $\leftarrow$ is not a mathematical equality. The statement

is meaningful as an update, while the equation $x=x+1$ has no real-number solution.

Input and return

A procedure header such as

DOUBLE(x)

names the procedure and its input. A statement

return 2x

ends the procedure and sends $2x$ back as its output.

Sequence

Unless a control structure says otherwise, instructions run from top to bottom.

x ← x + 2
y ← 3x
return y

For input $x=4$, the first line changes $x$ to $6$, the second stores $y=18$, and the procedure returns $18$. Skipping the intermediate update would produce the wrong trace.

Trace tables make changing state visible

A trace records an algorithm’s execution on one input. A trace table lists variable values after each relevant step.

For

MIX(a, b)
    a ← a + b
    b ← a - b
    return (a, b)

with input $(a,b)=(3,5)$:

Tracing one input does not prove an algorithm correct for every input, but it reveals how assignments and control flow behave. Section 5.2 will turn this observation into proof.

Reconstruct a scrambled pseudocode procedure on a command deck, then execute it one instruction at a time. The variable console exposes old and new values, while malformed step orders produce concrete output failures rather than a generic error message.

Conditional execution

An if statement chooses which instructions run.

ABSOLUTE(x)
    if x < 0
        return -x
    else
        return x

For $x=-7$, the condition is true and the procedure returns $7$. For $x=4$, the condition is false and it returns $4$.

The condition should cover every permitted input. If the algorithm says only

if x > 0
    return x

then its behavior is unspecified for $x=0$ and negative inputs. A missing case is an algorithm-design defect, not merely a formatting problem.

Several mutually exclusive cases may be written with else if:

SIGN(x)
    if x < 0
        return -1
    else if x = 0
        return 0
    else
        return 1

The output can be described by a piecewise function:

This is a bridge back to Chapter 4: an algorithm implements a function from permitted inputs to outputs.

Repetition with loops

A loop repeats a block of instructions. We first use a for loop when the number of repetitions is determined by a finite range.

SUM-TO(n)
    total ← 0
    for i ← 1 to n
        total ← total + i
    return total

For positive integer $n=4$, the variable $i$ takes values $1,2,3,4$:

The algorithm returns

More generally, after it finishes,

The loop body is indented. Moving the return statement inside the loop would stop after the first iteration, returning $1$ for every $n\ge1$.

While loops require progress

A while loop repeats while a condition remains true:

COUNTDOWN(n)
    while n > 0
        output n
        n ← n - 1

The update $n\leftarrow n-1$ moves $n$ toward the stopping condition. If that update were missing, positive input would cause an infinite loop.

When designing a while loop, ask:

1. What condition allows another iteration?

2. What changes during an iteration?

3. Why does that change eventually make the condition false?

These questions anticipate the termination proofs in Section 5.2.

Designing an algorithm from a specification

Suppose a robot stands at position $0$ on a straight track. It must collect packages at positions $1,2,\ldots,n$ and finish at position $n$. The robot understands:

• MOVE: advance one position;

• PICK: collect the package at the current position;

• REPEAT $n$ TIMES: execute an indented block $n$ times.

A correct compact algorithm is:

COLLECT-LINE(n)
    repeat n times
        MOVE
        PICK

The order matters. Performing PICK before MOVE would first try to collect at position $0$, where no package exists, and would leave the package at $n$ uncollected.

This example shows a useful design process:

1. state the starting configuration;

2. identify the repeated local action;

3. choose a loop that repeats it the required number of times;

4. trace a small input, including the smallest permitted input;

5. check both the final output and termination.

Program a package robot with movement, collection, condition, and repeat blocks. The robot animates the exact execution trace, penalizes unsafe or nonterminating control flow, and rewards compact programs that generalize across several track lengths.

Section bridge

We can now specify algorithms and trace what they do on examples. Examples alone cannot prove that every permitted input produces the promised output. Section 5.2 introduces preconditions, postconditions, loop invariants, and termination arguments so that algorithm correctness becomes a mathematical claim we can prove.