Algorithms as Precise Procedures

To ensure an algorithm is truly "correct," it must meet three strict criteria:

• Universality: It must work on any valid input within the defined domain.
• Termination: The procedure must eventually stop; a run that never returns provides no output.
• Correctness: The returned value must satisfy the goal for every possible valid input.

Note on Notation: In pseudocode, the symbol $\leftarrow$ is often used to mean "assign a value." For example, $x \leftarrow 2$ means we are setting the variable $x$ to 2. This is distinct from the mathematical equality symbol ($=$).

Example 1: The Max Entry Problem

To find the maximum value in a sequence, we can use a simple iterative approach:

MaxEntry ( A = (a1, a2, ..., aN) )
    best ← a1
    for i ← 2, ..., N
        if a_i > best
            best ← a_i
    return best

In this procedure, we pick the first element as our initial "best" candidate. We then loop through the remaining positions. If we find an entry larger than our current best, we update it. If $N=1$, the loop never runs, and the algorithm correctly returns $a_1$.

Algorithm vs. Function

While algorithms and functions are closely related, they are not identical. A function is a mapping where every input has exactly one output. However, a single problem might allow for multiple correct answers.

For instance, in a graph coloring problem, there might be many different ways to color a graph such that no two adjacent vertices share a color. An algorithm might produce different valid colorings depending on the order in which it processes the vertices, even though the "goal" (a proper coloring) is satisfied in every case.

Complex Procedures: Fibonacci and Greedy Coloring

Algorithms can be used to generate values based on rules or to construct complex structures.

Generating Fibonacci Numbers

The Fibonacci problem asks us to return the $N$-th term of the sequence where $f_1=1, f_2=1$, and $f_r = f_{r-1} + f_{r-2}$ for $r \geq 3$. A common algorithm uses a loop to update two variables simultaneously:

Fibonacci(N)
    a ← 1
    b ← 1
    repeat N-1 times:
        (a, b) ← (b, a + b)
    return a

The notation $(a, b) \leftarrow (b, a+b)$ is a shorthand for updating both values at once using their old values. This ensures that the calculation of the new $b$ uses the "old" $a$, not the newly updated one.

Constructing a Colouring

In graph theory, a "proper coloring" requires that no two adjacent vertices have the same color. A Greedy Coloring algorithm builds this assignment one vertex at a time:

GreedyCol (G = (V, E))
    let (v1, v2, ..., vn) be any ordering of V
    c ← empty assignment
    for i ← 1, 2, ..., n
        F ← colors of already-colored neighbors of vi
        c(vi) ← smallest positive integer not in F
    return c

This algorithm is "greedy" because it makes the best immediate choice (the smallest available color) without looking ahead to see if that choice will cause problems later. While this guarantees a proper coloring, it does not guarantee the minimum number of colors possible.

Exam Tip: When proving the correctness of a greedy algorithm, you often use induction. For coloring, you might prove that after $k$ steps, the first $k$ vertices are properly colored.

Summary Table of Algorithm Requirements